Q:

running time upper bound for b-tree

In the Art of Computer Programming, on the bottom of page 485

Suppose there's a B-tree of order m, and there are N keys, so the N+1 leaves appear on level l.
The numbers of nodes on levels 1,2,3... is at least 2,2[m/2],2[m/2]^2...

(Here [] denotes upper bound)
And Knuth give

N+1 >= 2[m/2]^(l-1)

My question is:
Shouldn't this be N+1 >= 2+2[m/2]+2[m/2]^2+...+2[m/2]^(l-1)?
What's the point of only taking nodes of the (l-1)th level into account?

A:

A branch node with k keys has k + 1 children.  So however many nodes there are on level l - 1, there must be more nodes on level l.
So N + 1 (the number of nodes on level l) is greater than the number of nodes on level l - 1.  Obviously the actual number of nodes on level l - 1 is greater than or equal to the minimum number of nodes on level l - 1.  So N + 1 ≥ 2⌈m / 2⌉l - 1.

