---------------------------------------------------------------------
Important: Remember that in a proper binary tree, the number of leaves is
one more than the number of internal nodes. (We already proved this!)
---------------------------------------------------------------------

Base case: Tree with 1 node. i=0, E=0, I=0; 0=0+2*0.

Inductive step:  If for any proper tree with 1<=r<=k internal nodes
_________________, then for any proper tree with k+1 internal nodes
_________________.

Proof:  Consider a proper binary tree T with k+1 internal nodes.
nodes.  Since T is proper, it must have two subtrees, T1 and T2.  Suppose
T1 has i internal nodes; then T2 must have _____________ internal nodes.  
Note that by a previously proven property of proper binary trees (above), 
T1 must have __________ leaves and T2 must have ____________ leaves.


Path lengths of the subtrees

If I1 and E1 are the internal and external path lengths for T1, and
I2 and E2 are the internal and external path lengths for T2, then
by the inductive hypothesis, 

      E1 = _________________        (1)
and
      E2 = _________________        (2)


The external path length of T

The external path length of T is the sum of the external path lengths of
T1 and T2 plus the number of leaves in T1 and T2, since each leaf is one
level deeper in T than in the subtree.  So 

      E = __________________________

which simplifies to

      E = E1 + E2 + k + 2           (3)


The internal path length of T

The internal path length of T is the sum of the internal path lengths of
T1 and T2 plus the number of internal nodes in T1 and T2, since each node
is one level deeper in T than in the subtree.  So

      I = ____________________      (4)


Putting it all together

Using equations (1) and (2) to substitute for E1 and E2 in equation (3) gives

      E = ________________________________________

which simplifies to

      E = ____________________      (5)

Rearranging (4), we see that 

      (I1 + I2) = _________________

Using this to substitute for I1 + I2 in (5) gives

     E = ___________________________

which simplifies to

     E = ___________________________

Voila!