Mmmm, Rosen...

Structural induction on full binary trees works as follows. Suppose you have a property P of trees, i.e., for each particular tree T, P(T) is either true or false. Suppose further that you prove that P holds on a single-node tree (consisting of a single root), and for any tree as in the picture above, if $\displaystyle P(T_1)$ and $\displaystyle P(T_2)$ hold, then P of the whole tree holds. In this case, P holds on all full binary trees.

The first step is to come up with P. Here it is easy: P(T) is $\displaystyle l(T) = i(T) + 1$. Next, prove P for the single-node tree. For the induction step, suppose $\displaystyle P(T_1)$ and $\displaystyle P(T_2)$ hold, i.e.,

$\displaystyle l(T_1)=i(T_1)+1$ and $\displaystyle l(T_2)=i(T_2)+1$. (*)

Let's call the whole tree T. Express $\displaystyle l(T)$ through $\displaystyle l(T_1)$, $\displaystyle l(T_2)$ and $\displaystyle i(T)$ through $\displaystyle i(T_1)$, $\displaystyle i(T_2)$. Try to prove P(T) from (*).