Proof of the factorial formula for binomial coefficients by induction

Proof

We use the recursive definition of the binomial coefficient and the factorial, and argue by induction on $n$. We prove the division-free form $k!\,(n-k)!\,\binom{n}{k} = n!$.

1. Lemma: for every natural number $n$, $\binom{n}{n} = 1$, and $\binom{n}{j} = 0$ for all $j > n$. We prove it by induction on $n$.
2. For $n = 0$, the definition gives $\binom{0}{0} = 1$ and $\binom{0}{j} = 0$ for $j \ge 1$.
3. Suppose the lemma holds for $n$. Let $j > n + 1$, and write $j = i + 1$ with $i > n$. By Pascal's rule, $\binom{n+1}{i+1} = \binom{n}{i} + \binom{n}{i+1} = 0 + 0 = 0$.
4. Also $\binom{n+1}{n+1} = \binom{n}{n} + \binom{n}{n+1} = 1 + 0 = 1$. This proves the lemma.
5. Main claim: for every $n$ and every $k \le n$, $k!\,(n-k)!\,\binom{n}{k} = n!$. We argue by induction on $n$.
6. For $n = 0$, only $k = 0$ occurs, and $0!\,0!\,\binom{0}{0} = 1 = 0!$.
7. Suppose the claim holds for $n$, and let $k \le n + 1$. If $k = 0$, then $0!\,(n+1)!\,\binom{n+1}{0} = (n+1)!$, since $\binom{n+1}{0} = 1$.
8. If $k = n + 1$, then $(n+1)!\,0!\,\binom{n+1}{n+1} = (n+1)!$ by the lemma.
9. Otherwise $1 \le k \le n$. Write $k = j + 1$ with $0 \le j \le n - 1$. Then $n + 1 - k = n - j$, and Pascal's rule gives $\binom{n+1}{k} = \binom{n}{j} + \binom{n}{j+1}$.
10. For the first term, $(j+1)! = (j+1) \cdot j!$. By the induction hypothesis for $j$, $(j+1)!\,(n-j)!\,\binom{n}{j} = (j+1) \cdot n!$.
11. For the second term, $n - j \ge 1$, so $(n-j)! = (n-j) \cdot (n-j-1)!$. By the induction hypothesis for $j + 1 \le n$, $(j+1)!\,(n-j)!\,\binom{n}{j+1} = (n-j) \cdot n!$.
12. Adding steps 10 and 11 gives $k!\,(n+1-k)!\,\binom{n+1}{k} = (j + 1 + n - j) \cdot n! = (n+1) \cdot n! = (n+1)!$.
13. This completes the induction. So $k!\,(n-k)!\,\binom{n}{k} = n!$ whenever $k \le n$.
14. Every factorial is at least $1$, since $0! = 1$ and $(m+1)! = (m+1) \cdot m!$. So $k!\,(n-k)! \ne 0$.
15. Dividing by $k!\,(n-k)!$ gives $\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$.