5
$\begingroup$

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r},$$ which can be proved combinatorically whether one particular element (among the $n$) is chosen or not. Now we use the obvious identity ${n \choose 1}=n$ and also that ${n \choose 2}=\sum_{i=1}^{n-1} i=\frac {n(n-1)}{2}$, both of which can be proved combinatorically and argue by induction, first on $r$ and then on $n$.

But this is a very lengthy process and I think not a good solution. Is there any shorter and better method to do this.

$\endgroup$
3
  • 1
  • $\begingroup$ Let $F(n,r)=\frac{n!}{r!(n-r)!}$. It is a not hard computation to show that $F(n,r)$ satisfies the Pascal Identity and the initial conditions for $\binom{n}{r}$. So $F(n,r)=\binom{n}{r}$ for all $n,r$. That is probably in essence what you did, and it is perfectly fine if one wants to write a non-counting proof. $\endgroup$ – André Nicolas Jun 21 '14 at 18:18
  • $\begingroup$ Resort to the natural language definition of $n \choose r$. The number of ways of choosing $r$ from $n$ is the sum of the number of ways two mutually exclusive events can occur: (a) choose a given item $S_n$ and then choose $r-1$ items from the remaining $n-1$; or (b) reject a given item $S_n$ and then choose $r$ items from the remaining $n-1$ $\endgroup$ – Marconius Jul 6 '15 at 21:42

Your Answer

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

Browse other questions tagged or ask your own question.