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

and

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

. Next, prove P for the single-node tree. For the induction step, suppose

and

hold, i.e.,

and

. (*)

Let's call the whole tree T. Express

through

,

and

through

,

. Try to prove P(T) from (*).