Is my proof by induction on binary trees correct?

Question

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}

Answer 1

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.$$

Answer 2

A much easier method without using induction is by counting the number of arrows pointing from parent nodes to child nodes.

For the root node, it's the target of $0$ arrows, and the origin of $2$ arrows. For each non-root stem node, it is the target of $1$ arrow and the origin of $2$ arrows. For each leaf node, it's the target of $1$ arrow and the origin of $0$ arrows. Thus we have $$arrow = 2\times1+2\times (S-1) + 0\times L=0\times1+1\times (S-1)+1\times L$$ thus $S=L-1$