Combinatorial proof of $\sum_{i = 0}^{n} \binom{i}{r - 1} = \binom{n + 1}{r}$ and then use result to find a formula for $1^2 + 2^2 + \ldots + n^2$ a) Give a combinatorial proof that for every $n \geq r \geq 1$ that:
$$\sum_{i = 0}^{n} \binom{i}{r - 1} = \binom{n + 1}{r}$$
And use (a) to concoct a formula for $1^2 + 2^2 + ... + n^2$

The starting-point is $\binom{i}{j}+\binom{i}{j+1}=\binom{i+1}{j+1}$, of which the combinatorial proof is famous. We can then telescope:$$\sum_{i=0}^n\binom{i}{r-1}=\sum_{i=0}^n\left(\binom{i+1}{r}-\binom{i}{r}\right)=\binom{n+1}{r}.$$The case $r=3$ gives $$\frac{n(n+1)(n-1)}{6}=\binom{n+1}{3}=\sum_{i=0}^n\binom{i}{2}=\sum_{i=0}^n\frac{i(i-1)}{2}=\frac{\sum_{i=1}^ni^2-\sum_{i=1}^ni}{2}.$$Hence$$\sum_{i=1}^ni^2=\sum_{i=1}^ni+\frac{n(n+1)(n-1)}{3}=\frac{n(n+1)}{2}+\frac{n(n+1)(n-1)}{3}=\frac{n(n+1)(2n+1)}{6}.$$
