HW 13: Proof By Induction

- 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)

- 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