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?
Best Answer
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}