Proof by 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

Induction step: Let T be a tree of height h with 2^hleaves. Add two leaves two each previous leave. This way we get 2*2^h leaves and and we increase the length of the tree by one.