Review question

# Can we show $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-2}{r-1}+\binom{n-3}{r-1}+\dotsb+\binom{r-1}{r-1}$? Add to your resource collection Remove from your resource collection Add notes to this resource View your notes for this resource

Ref: R8014

## Solution

1. Prove that $\sum_{r=0}^{n}\binom{n}{r}=2^n.$

Using the expression for the binomial theorem:

$(a+b)^n=\sum_{r=0}^{n}\binom{n}{r}a^n\,b^{n-r},$

if we set $a=b=1$ then

$(1+1)^n=2^n=\sum_{r=0}^{n}\binom{n}{r}1^n\,1^{n-r}=\sum_{r=0}^{n}\binom{n}{r},$

as required.

1. By considering the number of ways of choosing a set of $n$ people from a set of $2n$ people, or otherwise, prove that $\binom{2n}{n}=\binom{n}{0}^2+\binom{n}{1}^2+\dotsb+\binom{n}{n}^2.$

The expression

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

gives the number of ways of choosing $r$ objects from a set of $n$ objects, without replacement.

If we want to choose $n$ objects from $2n$ objects, one way of doing this is to line up the $2n$ objects and simply pick $n$ objects from them.

The number of ways of doing this is then $\dbinom{2n}{n}.$

Alternatively we could split the $2n$ objects into two equal groups of $n$ objects, then choose $r$ objects from the first group and $n-r$ from the second.

Summing over all the possible values of $r=\{0,\,1,\,2,\,\dotsb,n\}$ will give the total number of ways of doing this as $\sum_{r=0}^{n}\binom{n}{r}\binom{n}{n-r}.$

But we know by symmetry that $\dbinom{n}{r} = \dbinom{n}{n-r}$, and so we have $\dbinom{2n}{n} = \sum_{r=0}^{n}\dbinom{n}{r}^2.$

1. Prove that $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$

There are $\dbinom{n}{r}$ ways of choosing $r$ people from $n$ people.

If we now consider one specific person from among the $n$ people, say James, our set of $r$ people might include James or not.

If James is included, then there are $\dbinom{n-1}{r-1}$ ways of choosing the other $r-1$ people from the remaining $n-1$ people.

If James is excluded, then there are $\dbinom{n-1}{r}$ ways of choosing the $r$ people from the remaining $n-1$ people.

So there are $\dbinom{n-1}{r-1}+\dbinom{n-1}{r}$ ways in total of choosing $r$ people, hence

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

Alternatively, we could start with the right hand side of the given expression. We have

\begin{align*} \binom{n-1}{r-1}+\binom{n-1}{r} &= \frac{(n-1)!}{(r-1)!(n-r)!}+ \frac{(n-1)!}{r!(n-r-1)!} \\ &= \frac{r(n-1)!}{r(r-1)!(n-r)!}+ \frac{(n-r)(n-1)!}{r!(n-r)(n-r-1)!} \\ &= \frac{r(n-1)!}{r!(n-r)!}+ \frac{(n-r)(n-1)!}{r!(n-r)!} \\ &= \frac{r(n-1)!+(n-r)(n-1)!}{r!(n-r)!} \\ &= \frac{n(n-1)!}{r!(n-r)!} \\ &= \frac{n!}{r!(n-r)!}=\binom{n}{r}. \end{align*}

$[...]$ and hence, or otherwise, prove that $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-2}{r-1}+\binom{n-3}{r-1}+\dotsb+\binom{r-1}{r-1},$ where $r$, $n$ are positive integers with $1 \leq r \leq n-1$.

Using the formula above repeatedly, we find \begin{align*} \binom{n}{r} &= \binom{n-1}{r-1}+\binom{n-1}{r} \\ &= \binom{n-1}{r-1}+\left[\binom{n-2}{r-1}+\binom{n-2}{r}\right] \quad \text{etc.} \\ \end{align*} We can see that as this builds up we always have $\dbinom{n-a}{r}$ as the last term, but we want to end with $\dbinom{r-1}{r-1}$. If we note that $\dbinom{r}{r}=\dbinom{r-1}{r-1}=1$ then we know to continue until $n-a=r$ so $a=n-r$. \begin{align*} \binom{n}{r} &= \binom{n-1}{r-1}+\binom{n-2}{r-1}+\dotsb+\left[\binom{n-(n-r)}{r-1}+\binom{n-(n-r)}{r}\right] \\ &= \binom{n-1}{r-1}+\binom{n-2}{r-1}+\dotsb+\binom{r}{r-1}+\binom{r}{r} \\ &= \binom{n-1}{r-1}+\binom{n-2}{r-1}+\dotsb+\binom{r}{r-1}+\binom{r-1}{r-1} \end{align*}