CS212 Exams
Spring 1999 - Final

Solution to Induction

WARNING: You should seriously try to answer this question before looking at the solution -- it's just a good study skill. Also, some answers on this page may be more brief than you would want to put down in an actual exam. If you want any type of partial credit, you should write more than just the solution.

P(n): Let i be the number of interior node in an arbitrary tree of height n, then i 2^n-1 - 1.
Claim: For all n 1, P(n) is true.

Proof by strong induction on n

Base Case: n = 1

i 2^1-1 - 1 = 2⁰ - 1 = 1 - 1 = 0

This is correct, since a tree of height 1, has no interior nodes.

Induction Step: Let 1 k n

Assume i 2^k-1 - 1 for an arbitrary tree of height 1 k n. [I.H.]
Prove that i 2ⁿ - 1 for an arbitrary tree of height n + 1.

For an arbitrary tree of height n + 1, we know that the two sub-trees which are children of the root, have at most 2^k-1 - 1 interior nodes. [by I.H.]. Also observe that at least one sub-tree is of height n and it does not matter which sub-tree that is.

Thus i_L 2^k-1 - 1 and i_R 2^k-1 - 1.

Putting all this together for the tree of height n + 1, we get:

i = i_L + i_R + 1
i (2^k-1 - 1) + (2^n-1 - 1)  + 1
i 2(2^k-1) - 1 - 1 + 1
i 2^k - 1
i 2ⁿ - 1

Thus we have proven that the property P(n) holds for all n 1.

QED

Question

Return to CS 212 Final - Spring 1999