[proofplan]
We track two non-negative integer statistics along a derivation of $w$ from $S$ in a grammar in Chomsky normal form: the number of *terminal symbols* $T_i$ and the number of *variable symbols* $V_i$ in the current sentential form $\alpha_i$. In CNF every production is either binary ($A \to BC$ with $B, C$ variables) or unary ($A \to a$ with $a$ a terminal), so each step increments exactly one of $T_i, V_i$ by a controlled amount. A binary step keeps $T_i$ fixed and increases $V_i$ by one; a unary step increases $T_i$ by one and decreases $V_i$ by one. At the start, $(T_0, V_0) = (0, 1)$; at the end, $(T_n, V_n) = (n, 0)$ since $w \in \Sigma^*$ has length $n$. Solving the resulting linear system pins down the number of unary and binary steps uniquely, and their sum is $2n - 1$.
[/proofplan]
[step:Recall Chomsky normal form and fix notation]
A grammar $G = (V, \Sigma, P, S)$ is in [Chomsky normal form](/pages/???) iff every production in $P$ has one of the two shapes
\begin{align*}
A &\to BC, \qquad A, B, C \in V \text{ (a binary rule)}, \\
A &\to a, \qquad\quad A \in V,\ a \in \Sigma \text{ (a unary rule)}.
\end{align*}
In particular no production has right-hand side $\varepsilon$, and no right-hand side mixes terminals and variables. We consider a derivation
\begin{align*}
S = \alpha_0 \Rightarrow_G \alpha_1 \Rightarrow_G \cdots \Rightarrow_G \alpha_n = w,
\end{align*}
with $w \in \Sigma^*$, $|w| = n \ge 1$, and let $n$ denote the total number of steps (what we wish to evaluate). For each $i$ write
\begin{align*}
T_i &:= \#\{\text{terminal symbols in } \alpha_i\} = \text{number of indices } j \text{ with } \alpha_i(j) \in \Sigma, \\
V_i &:= \#\{\text{variable symbols in } \alpha_i\} = \text{number of indices } j \text{ with } \alpha_i(j) \in V.
\end{align*}
Since $\alpha_i \in (V \cup \Sigma)^*$, $T_i + V_i$ is the length of $\alpha_i$.
[/step]
[step:Record the boundary values of $T_i$ and $V_i$]
At $i = 0$: $\alpha_0 = S \in V$, hence
\begin{align*}
(T_0, V_0) = (0, 1).
\end{align*}
At $i = n$: $\alpha_n = w \in \Sigma^*$ with $|w| = n$, so every symbol of $\alpha_n$ is a terminal and
\begin{align*}
(T_n, V_n) = (n, 0).
\end{align*}
[/step]
[step:Compute the per-step increments of $T_i$ and $V_i$]
[claim:Each derivation step in CNF changes $(T_i, V_i)$ by $(0, +1)$ (binary step) or $(+1, -1)$ (unary step)]
A step $\alpha_i \Rightarrow_G \alpha_{i+1}$ selects a position $k$ with $\alpha_i(k) = A \in V$ and a production $A \to \gamma$, replacing that single variable occurrence by $\gamma$. Since $G$ is in CNF, $\gamma$ has one of two shapes:
*Binary rule* $A \to BC$ ($B, C \in V$): The one variable $A$ at position $k$ is replaced by two variables $B, C$. The number of terminals is unchanged, and the number of variables increases by $2 - 1 = 1$. Hence $(T_{i+1}, V_{i+1}) = (T_i, V_i + 1)$, i.e., increment $(0, +1)$.
*Unary rule* $A \to a$ ($a \in \Sigma$): The one variable $A$ is replaced by the single terminal $a$. The number of terminals increases by $1$, and the number of variables decreases by $1$. Hence $(T_{i+1}, V_{i+1}) = (T_i + 1, V_i - 1)$, i.e., increment $(+1, -1)$.
These are the only two cases because every CNF production is binary or unary.
[/claim]
[/step]
[step:Count binary and unary rules by solving a linear system]
Let $b$ be the number of binary steps and $u$ the number of unary steps in the derivation, so $b + u = n$ (the total number of steps is what we wish to find; at this stage $n$ is unknown to us, so we leave it as $b + u$ to be determined).
Telescoping the increments from the previous step over $i = 0, 1, \dots, n - 1$:
\begin{align*}
T_n - T_0 &= 0 \cdot b + 1 \cdot u = u, \\
V_n - V_0 &= 1 \cdot b + (-1) \cdot u = b - u.
\end{align*}
Substituting the boundary values $(T_0, V_0) = (0, 1)$ and $(T_n, V_n) = (n, 0)$:
\begin{align*}
u &= n - 0 = n, \\
b - u &= 0 - 1 = -1 \implies b = u - 1 = n - 1.
\end{align*}
[/step]
[step:Conclude the derivation has length $2n - 1$]
The total number of steps in the derivation is
\begin{align*}
(\text{binary steps}) + (\text{unary steps}) = b + u = (n - 1) + n = 2n - 1.
\end{align*}
This value is determined by the boundary conditions $(T_0, V_0) = (0, 1)$ and $(T_n, V_n) = (n, 0)$ alone — neither the particular order of binary/unary steps nor the particular rules applied affect the count. Therefore *every* $G$-derivation of $w$ has length exactly $2n - 1$, completing the proof.
[/step]
