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

We have the following definitions of Binomial Tree :
(i) Order 0 Binomial Tree contains 1 node. (This is the base tree)
(ii) Order 'k' Binomial Tree (also represented as T_k) can be made by taking two binomial trees of order k-1.

Example :

k = 0 (Single Node)

 o

k = 1 (2 nodes) 
[By taking two k = 0 order Binomial Trees]
 o
   \
     o

k = 2 (4 nodes)
[By taking two k = 1 order Binomial Trees]
   o
 /   \
o     o
       \
        o

Now by using the above information we will try to prove that the number of nodes of a Binomal Tree with height k has 2^k nodes.

The binomial tree of Order 0 represented as T₀ is the base binomial tree for k = 0 and we know that by the definiton stated above that T₀ has only 1 node.
Now a binomial tree T_k, k >= 0, T_k can be made by using two trees of T_k−1 and by definition each T_k−1 has
2^k-1 nodes. Thus, T_k has 2^k−1 + 2^k−1 = 2^k nodes.
Therefore it is proved by Mathematical Induction.