Use strong induction to prove number of vertices on complete tree is $2l-1$

Question

Can someone help me construct this proof using strong induction?

Use strong induction on $l$ to show that for all $l \geq 1$, a full binary tree with $l$ leaves has $2l-1$ vertices total.

Answer 1

"Strong" induction is really not needed here. For the inductive step, just pick any pair of leaves with the same parent and consider the tree obtained by removing them both; it has $l - 1$ leaves and you can proceed by "weak" induction. I imagine the proof you're "supposed" to write involves splitting your tree at its root and obtaining two trees of $k$ and $m$ leaves, where $m + k = l$; the sum of their numbers of vertices is one short of the correct number since you removed the original root.

Answer 2

Establish a basis: $l=1$ is a full binary tree isomorphic to $K_1$ which has $2(1)-1=1$ vertices.

Induction Hypothesis: Fix a $k$ and assume for all $l<k$ we have $2l-1$ vertices on a full binary tree with $l$ leaves.

Induction: Now consider the case when $l=k$. Suppose I have a graph $G$ that is a full binary tree with $k$ leaves. What happens when we delete two leaf vertices, say $u$ and $v$, that share a common internal vertex? Can we apply the induction hypothesis on $G-u-v$? If so, what happens when we add the two leaf vertices back in and reform $G$?