# Structural Inductions

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

-
Maybe if we knew the textbooks we could see what you're having trouble understanding, and find another way to say it. – Gerry Myerson Nov 20 '12 at 3:34
Discrete Mathematics and Its applications 7th edition Rosen and Discrete and combinatorial mathematics - an applied introduction 5th ed Grimaldi – Aaron Nov 20 '12 at 3:45
Check my edit please! – Aaron Nov 20 '12 at 4:00

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.
(2) is just counting the internal vertices of $T$ --- the $+1$ is the root of $T$. Its presence in (2) has nothing to do with the relation between $\ell$ and $i$. – Gerry Myerson Nov 20 '12 at 4:47