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$
 A: 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}.$$
A: Maybe not combinatorial, but maybe it helps somebody else for a proper idea.
\begin{align}
\binom{n+1}{r+1} &= \frac{n+1}{r+1}\binom{n}{r} \\
&=\binom{n}{r} + \frac{n-r}{r+1} \binom{n}{r} =\binom{n}{r} + \frac{n}{r+1} \binom{n-1}{r} =\binom{n}{r} + \binom{n}{r+1} \\
&=\binom{n}{r} + \binom{n-1}{r} + \binom{n-1}{r+1} \\
&= \dots \\
&=\sum_{i=0}^k \binom{n-i}{r} + \binom{n-k}{r+1} \, .
\end{align}
The last term vanishes for $k=n-r$. In that case use this formula for $r=2$ which immediately yields $1^2 + 2^2 + \dots + n^2$ in terms of simpler sums.
A: This combinatorical proof works:
${n+1\choose r}$ is the number of monotonic lattice paths along the edges of a grid with $r\times  (n+1-r)$ square cells($r$ columns, $n+1-r$ rows).
The way to prove this is that a monotonic path is given by a $n+1$ vector of the form $(\uparrow,\uparrow,\rightarrow,\uparrow,\rightarrow,\rightarrow,\dots)$ where the number of rightarrows is $r$.
Now, let's count this in a different way, for $i=0,\dots,n$, let $X_i$ the number of such vectors where the last $\rightarrow$ is in the $i+1$-th entry and therefore the next entries are uparrows. So, these vectors are determined by the first $i$ entries, where $r-1$ of them have to be rightarrows, hence $X_i={i\choose r-1}$
So, from this double counting you get what you want
$${n+1\choose r}=\sum_{i=0}^n{i\choose r-1}$$
To prove the other statement, use the formula above for $r=2$ and $r=3$ , you get 
$${n+1\choose 2}=\sum_{i=0}^ni$$
$${n+1\choose 3}=\sum_{i=0}^n\frac{i^2-i}{2}$$
So, multiplying the second equation by $2$ and adding the first equation, you get 
$$2{n+1\choose 3}+{n+1\choose 2}=\sum_{i=0}^n i^2$$
With a little bit of algebra, you can reduce this to 
$$\sum_{i=0}^n i^2=\frac{n(n+1)(2n+1)}{6}.$$
