CPSC 220 Fall 2006
HW 13: Proof By Induction

1. Use mathematical induction to prove the following property:

   n
   å	(4i-3) = n(2n-1), n>=1
   i=1

   Note that we could also have written this as follows:

   1 + 5 + 9 + ... + (4n-3) = n(2n-1)
   

2. Use structural induction on trees to prove the following property:

   A binary tree of height h has at most 2^h leaves.

   Hints:

   • Note that the tree need not be proper; you should prove it for any binary tree.
   • The induction is on the height of the tree. That is, in the inductive step you will assume the property for a tree of height k (or less) and prove it for a tree of height k+1.
   • Since we don't know anything about the structure of the tree, you will have to consider two cases:
     • The case where the root has only one subtree
     • The case where the root has two subtrees
     Of course, there's also the case there the root has no subtrees, but this is taken care of in the base case. The arguments for the two cases above are very similar, but it's clearest to deal with them separately.