Proving Pascal's identity

Question

So I came across Pascal's identity: Prove that for any fixed $r\geq 1$, and all $n\geq r$, $$ \binom{n+1}{r}=\binom{n}{r}+\binom{n}{r-1}. $$

I know you can use basic algebra or even an inductive proof to prove this identity, but that seems really cumbersome. I was wondering if anyone had a "cleaner" or more elegant way of proving it. For example, I think the following would be a decent combinatorial proof.

Proof: Let $S$ be a set with $n+1$ elements, and consider some fixed $x\in S$. There are $\binom{n+1}{r}\;\; r$-subsets of $S$--count them according to whether or not they contain $x$: there are $\binom{n}{r}$ not containing $x$, (each formed by choosing $r$ of the remaining $n$ elements in $S\setminus\{x\}$), and there are $\binom{n}{r-1}\;\; r$-sets containing $x$, (each formed by selecting an additional $r-1$ elements in $S\setminus\{x\}$).

Is that right? Are there any other efficient ways of doing it?

Answer 1

The algebra isn't really cumbersome at all

$$\binom{n}{r} + \binom{n}{r-1} = \frac{n!}{r!(n-r)!} + \frac{n!}{(r-1)!(n-r+1)!} \\ = \frac{n!(n-r+1) + n!(r)}{r!(n-r+1)!} = \frac{(n+1)!}{r!(n+1-r)!} = \binom{n+1}{r} $$

Answer 2

$(T+1)^{n+1}=(T+1) (T+1)^n$ and binomial coefficient are...

Answer 3

As you say, this can be proved without invoking the factorial representation -- just from the '${}_nC_r$ is the number of length-r distinct subsets of n objects' definition.

I would personally prefer to work backwards. To start with ${}_nC_r$ and examine combinations containing a particular element (w.l.o.g. #n) and those not containing that same element, yielding ${}_nC_r$ = ${}_{n-1}C_{r-1} + {}_{n-1}C _r$:

• Combinations containing element #n have $r-1$ available slots into which can be placed any of the remaining $n-1$ elements, so ${}_{n-1}C_{r-1}$ combinations.

• Combinations not containing element #n have all $r$ slots available, and $n-1$ elements that can go into them. So ${}_{n-1}C_r$.

So we get ${}_nC_r = {}_{n-1}C_{r-1} + {}_{n-1}C_r$ as required.