Finding an algebraic proof for $r{n \choose r} = n{n-1 \choose r-1}$

Question

I can't seem figure this proof out. How are both sides equal. $$r{n \choose r} = n{n-1 \choose r-1}$$

Answer 1

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

Answer 2

Hint: $${n \choose r} = \frac{n!}{r!(n-r)!} \qquad \textrm{and} \qquad r! = r \cdot (r-1)!$$

Answer 3

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.

Answer 4

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