Proof by mathematical induction.

Question

Proof by mathematical induction that for every integer h ≥ 0 there exists binary tree of height h with 2^h leaves.

Answer 1

Note that a full binary tree of height h has exactly 2^h leaves.

 

Proof:

 

Base: or h=0, the full tree has just the root node, which is a leaf. This is 2⁰ leaves.

 

Induction: Assume for some k≥0, that the height h full tree has 2^h leaves when h=k. Then when h=k+1, the full tree of height h is formed by letting the child nodes of it's root be roots of two height k full subtrees. So the tree will have 2^k+2^k = 2·2^k = 2^k+1 = 2^h leaves as desired.