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

Question

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?

Answer 1

(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*}$$

Answer 2

You can reduce this sum to something more manageable $$ \sum_{k=1}^Nk^2-\sum_{k=1}^Nk=\sum_{k=1}^Nk(k-1)=2\sum_{k=1}^N\binom{k}{2} $$ Now use the Pascal triangle identity $\binom{n}{m}+\binom{n}{m+1}=\binom{n+1}{m+1}$ to find $\binom{k}{2}=\binom{k+1}3-\binom{k}3$ to express this as a telescoping sum.

Interpretation of $\sum_{k=1}^N\tbinom{k}{2}$: Pick any integer number $k$ from $1$ to $N+1$ and then pick two numbers below $k$. This is the same as just picking three integers between $1$ and $N+1$.

Answer 3

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}