I am trying to make a proof by induction of the following theorem.
If T is a full binary tree with i internal vertices, then T has i + 1
terminal vertices and 2i + 1 total vertices.
I have done this so far but I am just starting to understand proofs and am stuck about what to do next.
Base Case:
P(1): 1 internal vertex => 1+1 = 2 terminal vertices
Induction:
Assume true: P(n): n internal vertices => n+1 terminal vertices
Show true: P(n+1): n+1 internal vertices => (n+1)+1 = n+2 terminal vertices
After this I am unsure of how to proceed.
SKETCH of proof: Let $T$ be a full binary tree with $i+1$ internal vertices. Let $v$ be a terminal vertex of maximal height, and let $u$ be the parent of $v$. $T$ is full, so $u$ has two children; let $w$ be the other child. Let $T'$ be the tree that remains when you remove $v$ and $w$ from $T$. Verify that $T'$ has $i$ internal vertices, and therefore by the induction hypothesis $i+1$ terminal vertices. One of these terminal vertices is $u$. When you restore $v$ and $w$ to $T'$ to recover $T$, you gain one internal vertex ($u$), you lose one terminal vertex ($u$), and you gain two terminal vertices ($v$ and $w$). The net change in internal vertices from $T'$ to $T$ is $+1$, as is the net change in terminal vertices, so $T$ must have $(i+1)+1=i+2$ terminal vertices.