Proving Pascal's identity

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?

To include more intuition. Let's say you want to know number of ways you can pick $k$ objects out of $n$ objects set. Assume you are holding one object. Either you want this object to be in your subset, or you want it excluded.

If you want this object to be in your subset, then there are $\binom{n-1}{k-1}$ remaining choices. Why? You include the one you were holding, so now you have $n-1$ left in the set. And since you decided to include it, you only have to pick $k-1$ more.

If you do not want this object to be in your subset, then there are $\binom{n-1}{k}$ remaining choices. Why? You are holding one object, so there are $n-1$ remaining, and you don't want it to be included in your subset, so you still have to pick $k$ objects from that $n-1$ set.

And both cases above represent "$n$ choose $k$" number of ways to pick $k$ objects from the set of $n$ objects. Hence the identity.

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} $$

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

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.