I can't seem figure this proof out. How are both sides equal. $$r{n \choose r} = n{n-1 \choose r-1}$$
Asked
Active
Viewed 600 times
2
-
2Did you try to apply the definition of ${n\choose r}$? – TZakrevskiy Mar 11 '14 at 20:14
-
1Have you even tried writing out the definition? – TMM Mar 11 '14 at 20:14
-
2What are your thoughts on the problem? What is the definition of $\binom{m}{k}$? – Servaes Mar 11 '14 at 20:14
-
@TZakrevskiy, I believe you mean the formula in terms of factorials. – vonbrand Mar 11 '14 at 20:15
-
Yeah I understand how its explained. I solved the combinatorial proof, and I know that the LHS would be r(n!/r!(n-r)!) but what i'm not sure about is how the r and the n is multiplied on each sides. – Guest999 Mar 11 '14 at 20:17
-
If you apply the definition, as TMM and TZakrevskiy have suggested, it really is clear. All you need to do is notice that $n-r=(n-1)-(r-1)$. – Chris Leary Mar 11 '14 at 20:18
4 Answers
3
$$r \binom {n}{r} = r \frac{n!}{r!(n-r)!}= \frac{n!}{(r-1)!(n-r)!}=n \frac{(n-1)!}{(r-1)!(n-r)!}= n \binom {n-1}{r-1}$$
user76568
- 4,542
-
How does it go from rn!r!(n−r)! to n!(r−1)!(n−r)! with the r disappearing? – Guest999 Mar 11 '14 at 20:22
-
-
As I commented to TMM, I would have included this if it was not already given. (+1) – robjohn Mar 11 '14 at 21:21
2
Here's a proof using the definition of binomial coefficients as counting certain subsets. Start with some $n$-element set $S$, say $S=\{1,2,\dots,n\}$, and consider the number of ways to choose an $r$-element subset $A$ of $S$ and choose an element $x$ in $A$. One way to count the choices is to notice that there are $\binom nr$ ways to choose $A$ and then, after choosing $A$, you have $r$ options for $x$, so the total number of options for $(A,x)$ is $\binom nrr$. Another way to count is to first choose $x$, for which there are $n$ possibilities, and then choose $A$. $A$ has to contain the $x$ that you just chose, and then it has to contain $r-1$ of the remaining $n-1$ elements of $S$. So the total number of possibilities is $n\binom{n-1}{r-1}$. The two ways of counting the same things have to agree, so your equation follows.
Andreas Blass
- 71,833
2
Here are a couple of approaches in addition to the approach used by Dror and TMM.
Generating Functions: $$ \frac{\mathrm{d}}{\mathrm{d}x}(1+x)^n=\sum_{r=1}^n r\binom{n}{r}x^{r-1} $$ $$ \begin{align} n(1+x)^{n-1} &=\sum_{r=0}^{n-1}n\binom{n-1}{r}x^r\\ &=\sum_{r=1}^nn\binom{n-1}{r-1}x^{r-1}\\ \end{align} $$ Compare the coefficients of $x^{r-1}$
Induction: Suppose it is true for row $n-1$ in Pascal's Triangle, then
$$ \begin{align} r\binom{n}{r} &=r\left[\binom{n-1}{r}+\color{#C00000}{\binom{n-1}{r-1}}\right]\\ &=r\binom{n-1}{r}+\color{#C00000}{(r-1)\binom{n-1}{r-1}+\binom{n-1}{r-1}}\\ &=\color{#00A000}{(n-1)\binom{n-2}{r-1}+(n-1)\binom{n-2}{r-2}}+\binom{n-1}{r-1}\\ &=\color{#00A000}{(n-1)\binom{n-1}{r-1}}+\binom{n-1}{r-1}\\ &=n\binom{n-1}{r-1} \end{align} $$
robjohn
- 345,667
1
Hint: $${n \choose r} = \frac{n!}{r!(n-r)!} \qquad \textrm{and} \qquad r! = r \cdot (r-1)!$$
TMM
- 9,976