Number of nodes at depth d in binomial tree

Question

So I have read that the number of nodes in a order k binomial tree at depth d is k choose d. However, I don't see where that result comes from. Anyone have a simple proof/intuition for this?

Answer 1

Here's a simple proof of the result using induction, though I think there's got to be a more elegant, intuitive argument that doesn't require induction.

We'll prove this statement by induction on n:

The number of nodes in the binomial tree of order n at depth d is n choose d.

The base case of n = 0 requires us to show that at depth d = 0 is (0 choose 0), which is 1. And that's true. Yay!

For the inductive step, assume this is true for n = k; we'll prove this for n = k + 1. Recall that a binomial tree of order k+1 can be formed by taking two binomial trees of order k and making one the child of the other. So if you pick any depth d, the number of nodes at depth d in the tree is given by

• the number of nodes at depth d from one tree of order k, and
• the number of nodes at depth d-1 from the other tree of order k, since that tree is shifted down one position.

Our inductive hypothesis tells us that the number of nodes here is then (k choose d) + (k choose d-1). Now, for Fun Facts About Binomial Coefficients! What do you get if you add (k choose d) + (k choose d-1)? That works out to (k+1 choose d). (Think Pascal's triangle for a nice easy proof, or work out the math).

We've got the claim holding for k+1, which finishes off our nice inductive proof.

All that's left to do now is to work out the intuition. :-)

Answer 2

@templatetypedef gives a formal(ish :) proof. Here's an informal proof:

In Pascal's triangle, the nodes in level N are the sum of level N-1, plus level N-1 shifted right.

In binomial trees, the tree of order N contains the tree of order N-1, plus the tree of order N-1 shifted down.

If we replace each level of a binomial tree with a count of the nodes in that level, the binomial tree construction becomes exactly the Pascal's triangle construction.