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