## G5BADS 2004-5 informal coursework 2

Prove by mathematical induction that a proper binary tree with
k levels contains 2^{k-1} leaves.

Proof:

** Basis of induction (k = 1)**: a perfectly balanced
tree with one level (just the root) has one leaf
(one node with no children). 1 = 2^{0} = 2^{1 - 1} so the
claim is correct for k = 1.

** Inductive step **: if the claim is true for proper binary trees
with n levels, it is true for proper binary trees with n+1 levels.

Assume that in a proper binary tree with n levels there are
2^{n-1} leaves. A perfectly balanced tree with n+1 levels
has twice more leaves (since every node on level n-1, which is a leaf in
a tree with n levels, now has two children which are leaves in a tree with
n+1 levels). So a proper binary tree
with n+1 levels has 2 * 2^{n-1} = 2^{n} leaves, which
is the same as 2^{(n+1)-1} leaves. If the claim holds for
a tree with n levels, it holds for a tree with n+1 levels.