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?
Best Answer
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.