0
$\begingroup$

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.

1 Answers 1

1

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.

  • 0
    @wazy: That’s right; and that means that $T$ must have had $i+2$ terminals.2012-10-05