I'm looking at 2 versions of textbook for structural induction and I just can't understand structural induction and how to draw the rooted trees from it. Does anyone have a good resource or can help me lighten up my brain so that I can understand it?
Maybe it's better if I give an example…
How would you approach this problem? (I know what rooted trees are)
A full binary tree is a graph defined through the following recursive
definition.
Basis step: A single vertex is a full binary tree.
Inductive step: If T1 and T2 are disjoint full binary trees with roots r1,
r2, respectively, the the graph formed by starting with a root r, and
adding an edge from r to each of the vertices r1; r2 is also a complete
binary tree.
Use structural induction to show that l(T) the number of leaves of a
complete binary tree T, is 1 more than i(T), the number of internal
vertices of T.
2
Best Answer
The base for the induction is the tree that's just a single vertex. That tree has one leaf and no internal vertices, so the statement is true for that tree.
Now let $T$ be a tree that's not just a single vertex, and make the induction hypothesis that the statement is true for all trees smaller than $T$. We get $T$ from trees $T_1$ and $T_2$, and we are assuming the statement is true for them. How many leaves does $T$ have? The leaves of $T$ consist of the leaves of $T_1$, together with the leaves of $T_2$, so $$\ell(T)=\ell(T_1)+\ell(T_2)\tag1$$ How many internal vertices does $T$ have? The internal vertices of $T$ are the internal vertices of $T_1$, the internal vertices of $T_2$, and the roots of $T$, so $$i(T)=i(T_1)+i(T_2)+1\tag2$$ By the induction hypothesis, $$\ell(T_1)=i(T_1)+1{\rm\ and\ }\ell(T_2)=i(T_2)+1\tag3$$ Put (3) into (1) to get $$\ell(T)=i(T_1)+i(T_2)+2\tag4$$ Now comparing (2) and (4), $\ell(T)=i(T)+1$, as we were to prove.
Let me know if there's anything that needs explaining (after you've tried to work through it on your own).