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?

  • 8
    $\begingroup$ HINT count the number of triplets $(a,b,c)$ for $a,b,c \in \{1,2,\ldots,n+1\}$ such that $c > \max(a,b)$ $\endgroup$ – r9m Mar 13 '14 at 5:47
  • $\begingroup$ @r9m ah I see now. Post that as an answer? $\endgroup$ – Guy Mar 13 '14 at 5:55
  • $\begingroup$ if you've already got it .. I won't have to :), plus I want to learn other answers .. this one is perhaps too common :D $\endgroup$ – r9m Mar 13 '14 at 5:55
  • $\begingroup$ @r9m Well the question needs to answered, otherwise it might bother others. Nothing much, just copy and paste the comment. $\endgroup$ – Guy Mar 13 '14 at 5:57
  • $\begingroup$ oh okay then. let's see. :) $\endgroup$ – Guy Mar 13 '14 at 5:57

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

  • $\begingroup$ your $\LaTeX$ isn't rendering? $\endgroup$ – Guy Mar 13 '14 at 11:55
  • $\begingroup$ Why? Everything is fine for me. I'm currently using Mozilla Firefox 27.0.1. Please see the screen shot I added. $\endgroup$ – Américo Tavares Mar 13 '14 at 11:58
  • 1
    $\begingroup$ Okay, I can read it now(from your screenshot, still not rendering). Better make a bug report on Mathematics Meta $\endgroup$ – Guy Mar 13 '14 at 12:03
  • 1
    $\begingroup$ The rendering issue was posted here. $\endgroup$ – Américo Tavares Mar 13 '14 at 12:47

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}


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$.

  • $\begingroup$ thanks for your answer, but as I said I needed a purely combinatorial approach for this. I have since found one with help from r9m's comment. Here is the solution $\endgroup$ – Guy Mar 13 '14 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.