3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What you have there is the best way to prove that identity that I know of. I'm sure there are other combinatorial interpertations of it, but that is the most natural one. Another way to prove this is to grind out the algebra, but why would you do that?-that doesn't really let you \emph{understand} it. $\endgroup$ – RougeSegwayUser Jan 30 '15 at 1:37
  • 2
    $\begingroup$ Yes, that is right, it is "the" combinatorial proof. I prefer something more tasty than $r$-sets. We have $n+1$ different doughnuts, including one chocolate one. We count the number of ways to pick $r$ doughnuts in two different ways. Another closely related combinatorial way of doing it is to use the identity $(1+x)^{n+1}=(1+x)^n(1+x)$. The coefficient of $x^r$ on the left-hand side is $\binom{n+1}{r}$. On the right, it is $\binom{n}{r}+\binom{n}{r-1}$. $\endgroup$ – André Nicolas Jan 30 '15 at 1:38
  • $\begingroup$ Of course whether a proof is simple or complex depends on your definition of $\binom{n}{r}$ $\endgroup$ – GEdgar Oct 27 '15 at 18:28
  • $\begingroup$ For more proofs of this identity, see: Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. $\endgroup$ – Martin Sleziak Feb 4 at 11:30
3
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is the $T$ for? Just a dummy variable or a special meaning? $\endgroup$ – fancynancy Jan 30 '15 at 1:40
  • $\begingroup$ It is a formal variable, for polynomials in the variable $T$ $\endgroup$ – ujsgeyrr1f0d0d0r0h1h0j0j_juj Jan 30 '15 at 1:41
  • $\begingroup$ $n \choose r$ is the coefficient of $T^r$ in the expension of $(T+1)^r$ $\endgroup$ – ujsgeyrr1f0d0d0r0h1h0j0j_juj Jan 30 '15 at 1:45
  • $\begingroup$ Very nice, although it does require the result that (a+b)^n expands to give the n-th row of Pascal's Triangle. $\endgroup$ – P i May 26 '16 at 18:14
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.