Prove Pascal's formula by induction

Question

I have Pascal's identity: $$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}.$$ How can I prove this using mathematical induction?

---

This is an exercise from Section 5.5 of Alan Tucker's Applied Combinatorics (6th edition). Identity (3) is Pascal's identity:

Answer 1

This is probably a mistake.

The textbook exercise says to use (3) to prove (3) as a hint, which is kind of dumb. It probably meant to tell you to first prove (3), then prove the rest of the identities using (3). Most natural proofs of Pascal's identity do not use induction.

There are trivial proofs "by induction".

That is, we can turn a normal proof into an inductive proof. For example:

We induct on $n$. For $n=1$, we have $\binom 1r = \binom0r + \binom{0}{r-1}$ since this is either saying $1=0+1$ when $r=1$, $1=1+0$ when $r=0$, or $0=0+0$ for all other $r$. Now suppose that Pascal's identity holds for $n-1$ instead of $n$. Without using this hypothesis in the least, we check that $$\binom{n-1}r + \binom{n-1}{r-1} = \frac{(n-1)!}{r! (n-1-r)!} + \frac{(n-1)!}{(r-1)!(n-r)!} = \frac{n!}{r!(n-r)!}\left(\frac{n-r}{n} + \frac rn\right) = \binom nr.$$ Therefore by induction the formula holds for all $n$.

This is stupid.

There are non-trivial proofs by induction if we allow ourselves some good starting hypotheses.

To do a decent induction proof, you need a recursive definition of $\binom nr$. Usually, that recursive definition is the formula $\binom nr = \binom{n-1}r + \binom{n-1}{r-1}$ we're trying to prove here. But if we start with something else, we can prove Pascal's identity. (Usually, the proof goes the other way, though.)

Here's one example:

Let $\binom nr$ be defined by the recursive formula $\binom nr = \sum_{k<n} \binom k{r-1}$, with base case $\binom n0 = 1$ for all $n$ and $\binom0r = 0$ for $r>0$. Then $\binom nr = \binom{n-1}r + \binom{n-1}{r-1}$.

Proof. We induct on $r$. When $r=1$, we can check from the recursive formula that $\binom n1 = n$, and this satisfies $\binom n1 = \binom{n-1}{1} + \binom{n-1}{0}$. Now suppose that Pascal's identity holds for all binomial coefficients $\binom{n'}{r'}$ with $r'<r$. Then \begin{align} \binom nr &= \sum_{k<n} \binom k{r-1} \\ &= \sum_{k<n} \binom{k-1}{r-1} + \sum_{k<n} \binom{k-1}{r-2} \\ &= \sum_{j<n-1} \binom j{r-1} + \sum_{j<n-1} \binom{j}{r-2} & \text{(setting $j=k-1$)} \\ &= \binom{n-1}{r} + \binom{n-1}{r-1}. \end{align} Therefore $\binom nr = \binom{n-1}r + \binom{n-1}{r-1}$ as well, and by induction the identity holds for all $n,r$.