Proof:

The empty tree is perfectly balanced and we have and and 0 = 2UP>0UP> - 1 as required.

Now consider a perfectly balanced tree t of depth k+1. It is of the form where the depth of l is k and the depth of r is also k. By the induction hypothesis we have that and .

$\Box$