4

For proving that:

$r{n \choose r}=n{n-1\choose r-1}$

I attempted it with:

$r{n\choose r}=\frac{rn!}{r!(n-r)!}=\frac{n!}{(r-1)!(n-r)!}$

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

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

I need help on what I did wrong and what is the correct method to prove this.

Najib Idrissi
  • 54,185
Itakura
  • 588

3 Answers3

1

The problem is at the beginning of your second calculation :

$n{n-1\choose r-1}=\frac{n(n-1)!}{(r-1)!(n-1-(r-1))!}$, not $\frac{n(n-1)!}{(r-1)!(n-(r-1))!}$

Augustin
  • 8,446
1

You found out that: $$r\binom{n}{r}=\frac{n!}{\left(r-1\right)!\left(n-r\right)!}$$ yourself.

Now realize that: $$\frac{n!}{\left(r-1\right)!\left(n-r\right)!}=n\frac{\left(n-1\right)!}{\left(r-1\right)!\left(n-r\right)!}=n\binom{n-1}{r-1}$$

drhab
  • 151,093
0

I don't agree with this proof, based on the formula for binomial coefficients in terms of factorials.

The reason is that to prove the formula, you need to first have proved the relation — at least in standard proofs.

Instead you can compare the coefficients of $x^{r-1}$ in the developments of $\bigl((1+x)^n\bigr)'$ and $\Bigl(\displaystyle\sum\limits_{r=0}^n \dbinom nr n^r\Bigr)'$.

Bernard
  • 175,478