Question

Suppose k is any natural number, k >= 0. Prove that the number of nodes in any binomial tree of height k is exactly 2^k.

Answer 1

For the binomial tree Bk,
1. There are 2k nodes.
2. The height of the binomial tree is k.
3. There are exactly ?ki ? nodes at depth i = 0,1,...,k.
4. The root has degree k, which is greater than that of any other node, moreover if the children of the root are numbered from left to right by k−1,k−2,...,0, child i is the root of the subtree Bi.

Proof of Property 1: Mathematical induction on k. The binomial tree B0 is the base binomial tree for k = 0. Clearly, by definition, B0 is a single node. Consider a binomial tree Bk, k ≥ 1. Since Bk is constructed using two copies of Bk−1, by the hypothesis, each Bk−1 has 2k−1 nodes. Thus, Bk has 2k−1 + 2k−1 = 2k nodes. Hence the claim.
Proof of Property 2: Mathematical induction on k. Clearly, B0 has height ’0’. By the hypothesis, Bk−1 has height k − 1. For Bk, one of the Bk−1’s becomes the root and hence the height increases by one when the other Bk−1 is attached. Thus, the height of Bk is k − 1 + 1 = k.
Proof of Property 3: Let D(k,i) be the number of nodes at depth i for a binomial tree of degree k. Since Bk is constructed using two copies of Bk−1, the nodes at depth (i − 1) of Bk−1 becomes the nodes at depth i for Bk. Therefore,
=
D(k, i) = D(k − 1, i) + D(k − 1, i − 1); = k−1Ci + k−1Ci−1;
(k − 1)! + (k − 1)! ; i!(k − 1 − i)! (i − 1)!(k − 1 − i + 1)!
(k−1)! ?1 1 ? = (k−i−1)!(i−1)! i+k−i ;
= k! ; i!(k − i)!
-1 7 9
= kCi
Proof of Property 4: Follows from the recursive definition of Bk.