Finding an algebraic proof for $r{n \choose r} = n{n-1 \choose r-1}$ I can't seem figure this proof out.
How are both sides equal.
$$r{n \choose r} = n{n-1 \choose r-1}$$
 A: $$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}$$
A: 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.
A: 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}
$$
A: Hint: $${n \choose r} = \frac{n!}{r!(n-r)!} \qquad \textrm{and} \qquad r! = r \cdot (r-1)!$$
