G5BADS 2004-5 informal coursework 2
Prove by mathematical induction that a proper binary tree with
k levels contains 2k-1 leaves.
Basis of induction (k = 1): a perfectly balanced
tree with one level (just the root) has one leaf
(one node with no children). 1 = 20 = 21 - 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
2n-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 * 2n-1 = 2n 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.