- 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.
- 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.\]
- 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\).
