I was working on my own inductive proof and I need some feedback since I couldn't find a similar proof over Math Exchange. I've got a feeling that this proof is around where it's supposed to be but still needs to be fixed a little. Please help me tell what makes this proof fall.
Prove that in a full binary tree, the number of leaves is greater in 1 than the number of vertices of ranked $2$ (internal vertices).
Proving in induction over $N$ the number of leaves in the tree
Base: For $N = 1$ the proof is simple, we can see that the number of leaves $= 1$ and the number of internal vertices $= 0$, 0 + 1 = 1 thus the assumption is correct for the base case.
Assume: We'll assume that for $N \in \mathbb{N}$ the number of leaves is greater by one than the number of internal vertices, and prove for $N+2$ (since $N+1$ will make the tree non-full).
Proof: Let $T$ be a full binary tree over $N+2$ leaves. We'll arbitrary choose an internal vertice and trim it's leaves, now we have $T'$ a tree on $N$ leaves and according to the assumption we know that the number of leaves is larger by $1$ than the number of internal vertices. If we let $n'_1$ be the number of leaves in $T'$ and $n'_2$ be the number of internal vertices in $T'$ we get that $n'_1 = n'_2+1$ from the assumption. Now if we recover the trimmed leaves we get that:
$$n_1 = n'_1 – 1 + 2 = n'_1 +2$$
$$n_2 = n'_2 +1$$
And since the proportions are kept, we know that $n_1 = n_2 + 1$
$\blacksquare$
Best Answer
Your proof is great; good job! Here's an alternate proof where I instead induct on $h$, the height of the full binary tree. To apply the induction hypothesis, I would think about removing the root instead of removing the leaves.
Base Case: For $h = 1$, the full binary tree consists of a single root node that is also a leaf (which is not an internal vertex), so this base case works (since $1 = 0 + 1$).
Induction Hypothesis: Assume that our claim holds for $h$, where $h \geq 1$.
It remains to prove that our claim holds for $h+1$. We consider a full binary tree $T$ of height $h+1$ with $m$ internal vertices and $n$ leaves. Now let $T_1$ and $T_2$ be the subtrees obtained by deleting the root node of $T$, which each have height $h$. Now let $m_k$ and $n_k$ denote the internal vertices and leaves (respectively) of $T_k$ for each $k \in \{1,2\}$. Now since $h+1 \geq 2$, we know that the deleted root node was not a leaf but an internal node, so we have that: \begin{align*} m &= m_1 + m_2 + 1 \\ n &= n_1 + n_2 \end{align*} But then since $T_1$ and $T_2$ both have height $h$, it follows by applying the induction hypothesis to each subtree that: \begin{align*} n_1 &= m_1 + 1 \\ n_2 &= m_2 + 1 \end{align*} But then it follows that: $$ n = n_1 + n_2 = (m_1 + 1) + (m_2 + 1) = (m_1 + m_2 + 1) + 1 = m + 1 $$ as desired. $\blacksquare$