[proofplan]
We prove the identity by splitting the integer $k$ into the five possible regions determined by the interval $[0,n]$: below $0$, equal to $0$, strictly between $0$ and $n$, equal to $n$, and above $n$. In the out-of-range and boundary cases, the zero-extension definition gives the required values directly. In the interior case $1 \leq k \leq n-1$, all three binomial coefficients are in range, so the identity follows from expanding the factorial definitions and reducing to a common denominator.
[/proofplan]
[step:Handle lower indices below zero by zero-extension]
Assume $k < 0$. Then $k < 0$, $k-1 < 0$, and $k < 0$ as lower indices for the binomial coefficients with upper indices $n$ and $n-1$. By the zero-extension definition,
\begin{align*}
\binom{n}{k} = 0.
\end{align*}
Also,
\begin{align*}
\binom{n-1}{k-1} = 0.
\end{align*}
And
\begin{align*}
\binom{n-1}{k} = 0.
\end{align*}
Therefore
\begin{align*}
\binom{n}{k} = 0 = 0 + 0 = \binom{n-1}{k-1} + \binom{n-1}{k}.
\end{align*}
[/step]
[step:Verify the left boundary case $k = 0$]
Assume $k = 0$. Since $0 \leq 0 \leq n$, the factorial definition gives
\begin{align*}
\binom{n}{0} = \frac{n!}{0!n!} = 1.
\end{align*}
Since $-1 < 0$, the zero-extension definition gives
\begin{align*}
\binom{n-1}{-1} = 0.
\end{align*}
Since $0 \leq 0 \leq n-1$, the factorial definition gives
\begin{align*}
\binom{n-1}{0} = \frac{(n-1)!}{0!(n-1)!} = 1.
\end{align*}
Substituting $k = 0$, we obtain
\begin{align*}
\binom{n}{k} = 1 = 0 + 1 = \binom{n-1}{k-1} + \binom{n-1}{k}.
\end{align*}
[/step]
[step:Expand the factorial definitions in the interior range]
Assume $1 \leq k \leq n-1$. Then $0 \leq k \leq n$, $0 \leq k-1 \leq n-1$, and $0 \leq k \leq n-1$, so all three binomial coefficients are in range for the factorial definition. Hence
\begin{align*}
\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!(n-k)!}.
\end{align*}
Also,
\begin{align*}
\binom{n-1}{k} = \frac{(n-1)!}{k!(n-1-k)!}.
\end{align*}
Because $k \geq 1$ and $n-k \geq 1$, the identities $k! = k(k-1)!$ and $(n-k)! = (n-k)(n-1-k)!$ allow both fractions to be written with common denominator $k!(n-k)!$:
\begin{align*}
\frac{(n-1)!}{(k-1)!(n-k)!} = \frac{k(n-1)!}{k!(n-k)!}.
\end{align*}
And
\begin{align*}
\frac{(n-1)!}{k!(n-1-k)!} = \frac{(n-k)(n-1)!}{k!(n-k)!}.
\end{align*}
Adding the two expressions gives
\begin{align*}
\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{k(n-1)! + (n-k)(n-1)!}{k!(n-k)!}.
\end{align*}
Factoring the numerator,
\begin{align*}
\frac{k(n-1)! + (n-k)(n-1)!}{k!(n-k)!} = \frac{n(n-1)!}{k!(n-k)!}.
\end{align*}
Since $n! = n(n-1)!$, this is
\begin{align*}
\frac{n!}{k!(n-k)!} = \binom{n}{k}.
\end{align*}
Therefore
\begin{align*}
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.
\end{align*}
[guided]
The interior case is the only case where an actual algebraic computation is needed. Assume $1 \leq k \leq n-1$. These inequalities serve two purposes. First, they ensure that $k$ is a valid lower index for the upper index $n$, that $k-1$ is a valid lower index for the upper index $n-1$, and that $k$ is a valid lower index for the upper index $n-1$. Therefore the zero-extension clause is not used in this case; all three binomial coefficients are given by factorials:
\begin{align*}
\binom{n}{k} = \frac{n!}{k!(n-k)!}.
\end{align*}
Also,
\begin{align*}
\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!(n-k)!}.
\end{align*}
And
\begin{align*}
\binom{n-1}{k} = \frac{(n-1)!}{k!(n-1-k)!}.
\end{align*}
The second use of $1 \leq k \leq n-1$ is that both $k$ and $n-k$ are positive integers. Thus $k! = k(k-1)!$ and $(n-k)! = (n-k)(n-1-k)!$. These identities justify the common-denominator step. For the first summand, multiplying the denominator $(k-1)!(n-k)!$ by $k$ gives $k!(n-k)!$, so the numerator must also be multiplied by $k$:
\begin{align*}
\binom{n-1}{k-1} = \frac{k(n-1)!}{k!(n-k)!}.
\end{align*}
For the second summand, multiplying the denominator $k!(n-1-k)!$ by $n-k$ gives $k!(n-k)!$, so the numerator must also be multiplied by $n-k$:
\begin{align*}
\binom{n-1}{k} = \frac{(n-k)(n-1)!}{k!(n-k)!}.
\end{align*}
Now both fractions have the same denominator, so we add their numerators:
\begin{align*}
\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{k(n-1)! + (n-k)(n-1)!}{k!(n-k)!}.
\end{align*}
The numerator has the common factor $(n-1)!$, and the remaining coefficient is $k + (n-k) = n$. Hence
\begin{align*}
\frac{k(n-1)! + (n-k)(n-1)!}{k!(n-k)!} = \frac{n(n-1)!}{k!(n-k)!}.
\end{align*}
Finally, by the defining recursion for factorials, $n! = n(n-1)!$, so
\begin{align*}
\frac{n(n-1)!}{k!(n-k)!} = \frac{n!}{k!(n-k)!} = \binom{n}{k}.
\end{align*}
Thus, in the interior range,
\begin{align*}
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.
\end{align*}
[/guided]
[/step]
[step:Verify the right boundary case $k = n$]
Assume $k = n$. Since $0 \leq n \leq n$, the factorial definition gives
\begin{align*}
\binom{n}{n} = \frac{n!}{n!0!} = 1.
\end{align*}
Since $0 \leq n-1 \leq n-1$, the factorial definition gives
\begin{align*}
\binom{n-1}{n-1} = \frac{(n-1)!}{(n-1)!0!} = 1.
\end{align*}
Since $n > n-1$, the zero-extension definition gives
\begin{align*}
\binom{n-1}{n} = 0.
\end{align*}
Substituting $k = n$, we obtain
\begin{align*}
\binom{n}{k} = 1 = 1 + 0 = \binom{n-1}{k-1} + \binom{n-1}{k}.
\end{align*}
[/step]
[step:Handle lower indices above $n$ by zero-extension]
Assume $k > n$. Then $k > n$, so the zero-extension definition gives
\begin{align*}
\binom{n}{k} = 0.
\end{align*}
Also $k > n > n-1$, so
\begin{align*}
\binom{n-1}{k} = 0.
\end{align*}
Finally, $k > n$ implies $k-1 \geq n > n-1$, so
\begin{align*}
\binom{n-1}{k-1} = 0.
\end{align*}
Therefore
\begin{align*}
\binom{n}{k} = 0 = 0 + 0 = \binom{n-1}{k-1} + \binom{n-1}{k}.
\end{align*}
[/step]
[step:Conclude the identity for every integer lower index]
For a fixed integer $n \geq 1$, every integer $k \in \mathbb{Z}$ lies in exactly one of the five cases $k < 0$, $k = 0$, $1 \leq k \leq n-1$, $k = n$, or $k > n$. The preceding steps prove
\begin{align*}
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
\end{align*}
in each case. Hence the identity holds for every integer $n \geq 1$ and every integer $k \in \mathbb{Z}$.
[/step]
