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

What does the binomial theorem give as the value of \((a+b)^n\)? What about \((1+a)^n\)?

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

Could we split our group of people into two groups of size \(n\)?

If we take 1 person from the first group, how many people do you have to take from the second to choose \(n\) people overall?

What if we take \(r\) people from the first group?

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

Could we write down the two factorial representations of \(\dbinom{n-1}{r-1}\) and \(\dbinom{n-1}{r}\)?

Or could we imagine a bag of \(n\) objects, and picking \(r\) from it?

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

We’ve just found an expression for \(\dbinom{n}{r}\) — how is this useful?