0
$\begingroup$

I am wokring with proof by structural induction, and I'm not sure if I have solved the task correctly so far, I am also stuck at the last part of my proof.

The number of nodes in a full binary tree, written n(T), defined recursively:

$$n(T) = 1$$ $$n(T_1, T_2) = 1 + n(T_1) + n(T_2)$$

The number of leaves of a full binary tree, written l(T), defined recursively:

$$l(T) = 1$$ $$l(T_1, T_2) = l(T_1) + l(T_2)$$

Now I'm to prove that $n(T) = (2l(T) – 1)$ for all full binary trees $T$, using structural induction.

My proof this far:

Proof by structural induction:

  • Basis step: Show that the result holds for all elements specified in the basis step of the recursive definition to be in the set.
  • Recursive step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements

Let P(n) state that $n(T) = (2l(T) – 1)$ is true for all elements of the set that are generated by $n$ or fewer applications of the rules in the recursive step $n(T) = 1 + n(T_1) + n(T_2)$

To proof: $n(T) = (2l(T) – 1)$

Using the recursive definitions from above:

  • Basis step: $$n(1) = (2l(1) – 1) = ( 2(1) – 1) = (2 -1) = 1 = 1 $$ $$n(2) = (2l(2) – 1) = ( 2(2) – 1) = (4 -1) = 3 = 1 + 1+ 0 = 1 + n(T_1) + n(T_0)$$
  • Recursive step: THIS IS WHERE I'M STUCK.

Also, how does my proof look, have I missed or misunderstood something?

$\endgroup$
0
$\begingroup$

Using your notation,

$$n(T_1, T_2)= 1+n(T_1)+n(T_2)$$ $$l(T_1, T_2)=l(T_2)+l(T_2)$$

If we have $n(T_1)=2l(T_1)-1$ and $n(T_2)=2l(T_2)-1$,

Then \begin{align} n(T_1, T_2) &= 1 + n(T_1) + n(T_2) \\ &= 1+2l(T_1)-1 + 2l(T_2)-1\\ &= 2(l(T_1) +l (T_2))-1 \\ &= 2l(T_1, T_2) -1 \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.