Question

Define the height of a tree as the maximum number of edges between the root and any leaf. We consider the height of an empty tree to be -1, and the height of a tree consisting of a single node to be 0. Prove by induction that every non-empty binary tree of height h contains fewer than 2h+1 nodes.

Answer 1

To prove : Every non-empty binary tree of height h contains fewer than 2^(h+1) nodes.
Proof by induction
Base Case: h = 0. Tree contain only one node.
Less than 2^(0+1) = 2 , so the base case satisfies the I.H.

Induction Hypothesis: Suppose that the result holds for some k >= 0; i.e.,
a tree of height k has lesser than 2^(k+1) nodes.

for h = k+1
  
By definition of leaf, all the nodes at depth k+1 are leaf nodes.
we know there are at most 2^(k+1) leaves. If we remove all the leaf nodes, we are
left with a tree of height k. Thus the total number of nodes in T is at
most 2^(k+1) {Leaves count} + 2^(k+1) - 1 {by induction Hypothesis}

=> 2*(2^(k+1)) - 1 = 2^(k+1+1) - 1. which is lesser than (2^(k+1+1)) . Hence the hypothesis holds for k+1(proved).