# Show that ${n\choose r}={{n-1}\choose{r-1}}+{{n-1}\choose {r}}$. [duplicate]

Show that ${n\choose r}={{n-1}\choose{r-1}}+{{n-1}\choose {r}}$.

My try:

$$\dfrac{n!}{(n-r)!\;r!}=\dfrac{(n-1)!}{(n-r)!(r-1)!}+\dfrac{(n-1)!}{(n-1-r)!\;r!}$$ Multiplying all terms by $r!(n-r)!$ $$n!=r(n-1)!+(n-1)!(n-r)$$ Dividing everything by $(n-1)!$ $$n=r+(n-r)$$ $$n=n$$

Is this correct?

• It looks like you are actually multiplying by $r!(n - r)!$. Commented Mar 21, 2017 at 1:20
• The combinatorial proof is often seen as more elegant and more desirable. Any way of choosing $r$ people from $n$ total people where one of the persons is special is either choosing the special person and $r-1$ other people from the $n-1$ non-special people or not choosing the special person while choosing $r$ people from the $n-1$ non-special people. Commented Mar 21, 2017 at 1:30

Other than the typo, I don't see a problem with it. Because you are dividing, I think it would help if you stated that $a! \neq 0.$

You have a typo on the line "multiplying all terms by...", $(r−1)!$ should be $r!$.

Looks good. You have a typo on the line "multiplying all terms by...", $(r-1)!$ should be $r!$.

Ideally you would write this proof backwards, starting with $n=n$ and finishing with what you are trying to prove.

Combinatorial Proof:

Let $A= \big\{1,2, \ldots,n\big\}$. there are $\binom{n}{r}$ ways to form r-combinations $S$ of $A$.

we can count the number of r-combinations $S$ of $A$ in a different way. Every r-combination $S$ of $A$ either contains the element $1$ or not. if $1 \in S$, the number of ways to form S is $\binom{n-1}{r-1}$. if $1\notin S$, the number of ways to form $S$ is $\binom{n-1}{r}$. thus we have:

$$\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}$$

source:Principles and Techniques in Combinatorics

$$\dfrac{n!}{(n-r)!\;r!}=\dfrac{(n-1)!}{(n-r)!(r-1)!}+\dfrac{(n-1)!}{(n-1-r)!\;r!}$$ Multiplying all terms by $r!(n-r)!$ (rather than $(r-1)!(n-r)!$) $$n!=r(n-1)!+(n-1)!(n-r) = r(n-1)!+(n-1)!n - r(n-1)! = n!$$

But it's usually better to start with one side and ending up at the other side. So:

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

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

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

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

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

$${{n}\choose {r}}$$