Page 505, Exercise 3

   This proof is similar to the one given in problem 7, page 449.  That problem showed the relation between the number of elements in an F-heap and the Fibonacci numbers.  This relation was expressed by the formula: N_i = F_i+2, i ≥ 0.   In the current problem, we want to prove the minimum number of elements for a given level of an AVL tree is: N_h = F_h+2-1, h ≥ 0.

Induction Base: The statement is true for h=0 since an AVL tree with a height of zero contains only the root node.

Induction Hypothesis: Assume that for k= 2 to m,  N_k= F_k+2-1.

Induction Step: Prove that N_k+1 = F_k+1+2-1.  This is equivalent to N_k+1 = F_k+3-1.  This is obviously true since we have only shifted the formula right by two positions.