The following is an attempt to prove that a certain relation (4) holds, between the number of leaves, and stems in a perfect binary tree.
A stem will be defined as any node that has child nodes, and leaves those with none. For the purposes of this problem, each node can only have 2 or 0 children.
I belive I have made a mistake in the inductive step. I re-used the
induction hypothesis after I obtained an equivalent formula for it. Here I
ask: Is this permitted?
In all equations, $S_n$ represents the number of stems, $L_n$ the number of leaves, and $n$ the height of the longest branch, starting from zero.
Base Case
When we have just one leaf node (a single dot), the relation (1) holds when n=0:
\begin{equation}\tag{1}
S_n=L_n-1\ ,\ where\ L_n=2^n
\end{equation}
Induction Hypothesis
For an arbitrary but constant tree height, the relation $S_k=L_k-1\ ,\ where\ L_k=2^k$ is true.
Inductive Step
The act of changing $L_k$ end leaves to stems is the net effect bellow, which is equivalent to $(+L_k)\ leaves$ and $(+L_k)\ stems$:
\begin{equation}
net\ effect = -L_k\ leaves \\
\quad +L_k\ stems\\
\quad +2L_k\ leaves.
\end{equation}
So the relations for each next step are $S_{k+1}=S_k+L_k$ and $L_{k+1}=L_k+L_k$ .
We want to see if (2) is true. Since $S_{k+1}=S_k+L_k$ and $L_{k+1}=L_k+L_k$ , (2) becomes (3) .
\begin{equation}\tag{2}
S_{k+1}=L_{k+1}-1
\end{equation}
\begin{equation}\tag{3}
S_k+L_k=L_k-1+L_k
\end{equation}
Since $L_k$ is added to both sides of (1), we can cancel and obtain our inductive hypothesis.
Now since the base case is true; and the inductive hypothesis implies the next configuration regardless of the starting configuration, it is implied that the relation bellow is true for all cases.
\begin{equation}\tag{4}
S_n=L_n-1\ ,\ where\ L_n=2^n
\end{equation}
Best Answer
Here's a simpler inductive proof:
Induction start: If the tree consists of only one node, that node is clearly a leaf, and thus $S=0$, $L=1$ and thus $S=L-1$.
Induction hypothesis: The claim is true for trees of less than $n$ nodes.
Inductive step: Let's assume we've got a tree of $n$ nodes, $n>1$. Then its root node obviously isn't a leaf, but a stem, and thus there are two sub-trees attached to it, both obviously with less than $n$ nodes. Therefore for these trees, we have $S_k = L_k-1$. Thus we have $$S = 1 + S_l + S_r = 1 + (L_1-1) + (L_2-1) = L_1 + L_2 - 1 = L-1.$$