Use mathematical induction to prove the following property:
(4i-3) = n(2n-1), n>=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 2h leaves.
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
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.