Prove $1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3}$

Prove that:

$$ 1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3} $$

Now, if I simplify the right hand combinatorial expression, it reduces to $\frac{n(n+1)(2n+1)}{6}$ which is well known and can be derived by the method of common differences.

This though is in the exercise sheet related to combinatorics and specifically the method of proof by double counting. I can't figure out how to do that. Specifically this looks like "choose 2 objects from n+1 and then choose 3 objects from n+1 twice." But that's that, I can't find a link between that and the sum of squares. Any help?

The identity is an application of Worpitzky's identity involving Eulerian numbers. Worpitzky's theorem states: $$x^n=\sum_{k=0}^{n}A(n,k) \binom{x+k}{n}$$ where Eulerian number $A(n, k)$ is defined to be the number of permutations of the numbers 1 to n in which exactly k elements are greater than the previous element (permutations with k "ascents"). (Worpitzky's identity is not hard to prove using induction btw)

By Worpitzky's identity, for integer $k\geq 1, k^2=\sum_{i=0}^{2} A(2,i) \binom{n+i}{2} = A(2,0)\binom{k}{2} +A(2,1)\binom{k+1}{2}=\binom{k}{2}+\binom{k+1}{2}$.

So the sum of the squares of the first $n$ positive integers is \begin{equation} \begin{aligned} \sum_{i=1}^{n} k^2 &=\sum_{i=1}^{n} \binom{k}{2} + \sum_{i=1}^{n} \binom{k+1}{2}\\ &= \binom{n+1}{3}+\binom{n+2}{3}\\ &=\frac{1}{6}n(n+1)(2n+1) \end{aligned} \end{equation} This equality follows from the following identity for the rising sum of binomial coefficients: $$\sum_{j=0}^{n} \binom{j}{m} = \binom{n+1}{m+1}$$

Similarly, we can find the sum of first n cubic numbers. For integer $k\geq 1$, Worpitzky's identity says that $k^3=A(3,0)\binom{k}{3}+A(3,1)\binom{k+1}{3}+A(3,2)\binom{k+2}{3}=\binom{k}{3}+4\binom{k+1}{3}+\binom{k+2}{3}$

Same as we just did in the last case, the sum of the cubes of the first $n$ positive integers is \begin{equation} \begin{aligned} \sum_{i=1}^{n} k^3 &=\sum_{i=1}^{n} \binom{k}{3} + 4\sum_{i=1}^{n} \binom{k+1}{3}+\sum_{i=1}^{n} \binom{k+2}{3}\\ &= \binom{n+1}{4}+4\binom{n+2}{4}+\binom{n+3}{4}\\ &=\frac{1}{4}(n^4+2n^3+n^2) \end{aligned} \end{equation}

(Exercise 1.42 in Balakrishnan, Combinatorics, Schaum's Outline of Combinatorics). From

$$\binom{k}{1}+2\binom{k}{2}=k+2\frac{k\left( k-1\right) }{2}=k^{2},$$

we get

$$\begin{eqnarray*} S &:&=\sum_{k=1}^{n}k^{2}=\sum_{k=0}^{n}\binom{k}{1}+2\binom{k}{2} =\sum_{i=1}^{n}\binom{k}{1}+2\sum_{k=1}^{n}\binom{k}{2} \\ &=&\binom{n+1}{2}+2\binom{n+1}{3} \\ &=&\frac{n\left( n+1\right) \left( 2n+1\right) }{6}. \end{eqnarray*}$$