# Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$?

I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:

$$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$

I really have no idea why this statement is true. Can someone please explain why this is true and if possible show how to arrive at one given the other?

-
...and there is also math.stackexchange.com/questions/47509/… – Grigory M Jun 28 '11 at 6:40
OP does not show any attempt not to advance research and previous work. For questions so people give negative feedback but why now do not? There are also cases where the question is put on hold and now they do not. Can, please be more consistent? – Luis Felipe Oct 22 '15 at 15:46

You can easily prove it by induction.

One way to find the coefficients, assuming we already know that it's a degree $3$ polynomial, is to calculate the sum for $n=0,1,2,3$. This gives us four values of a degree $3$ polynomial, and so we can find it.

The better way to approach it, though, is through the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$ This identity is true since in order to choose a $(k+1)$-subset of $n+1$, you first choose an element $t+1$, and then a $k$-subset of $t$.

We therefore know that $$\sum_{t=0}^n A + Bt + C\binom{t}{2} = A(n+1) + B\binom{n+1}{2} + C\binom{n+1}{3}.$$ Now choosing $A=0,B=1,C=2$, we have $$A+Bt + C\binom{t}{2} = t^2.$$ Therefore the sum is equal to $$\binom{n+1}{2} + 2\binom{n+1}{3}.$$

-
That's a good method: +1! Concerning the polynomial approach, I think it could be enhanced by noticing that if $p_k(n)=\sum_{i=1}^n i^k$ then, extending what you wrote, $p_k\in\mathbb Q[n]$, $\partial p_k=k+1$, and $n(n+1)\,\Big|\,p_k$ for every $k$. For $k=2$ this reduces to 2 the coefficients to be found making this approach equally worth, isn't it? – AndreasT Mar 30 '13 at 15:58
That's a great approach. Can you tell me what's the name of this identity : $\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}$. Is it the Pascal triangle? – hlapointe Oct 21 '15 at 14:37
@hlapointe It probably does have a name but I can't think of any! Do let me know if you find out. – Yuval Filmus Oct 21 '15 at 15:27
I learned this as the hockey stick identity. – Slade Jan 11 at 9:09

Another way (by Euler, I think), from the geometric sum:

$$1 + x + x^2 + \cdots + x^n = \frac{x^{n+1}-1}{x-1}$$

Differentiate both sides and multiplying by $x$:

$$x + 2 x^2 + 3 x^3 + \cdots + n x^{n} = \frac{n x^{n+2}-(n+1) x^{n+1} +x}{(x-1)^2}$$

Differentiate once more, we get on the LHS

$$1 + 2^2 x + 3^2 x^2 + \cdots + n^2 x^{n-1}$$

which, evaluated at $x=1$ gives our sum $\sum_{k=1}^n k^2$. What remains (straightforward, but tedious) is to compute the derivative on the RHS, and evaluate it at $x \to 1$ (eg, with L'Hopital rule).

It should be evident that this procedure also can be applied (though it also turns more cumbersome) for sums of higher powers.

(Update) here's a concrete derivation, using binomial expansion of the LHS around $(x-1)$:

$$g(x)=\frac{x^{n+1}-1}{x-1}=\frac{(x-1+1)^{n+1}-1}{x-1}=\\=(n+1)+{n+1 \choose 2}(x-1)+{n+1 \choose 3}(x-1)^2+O((x-1)^3)$$

Hence $$(g'(x) \, x)'={n+1 \choose 2}+{n+1 \choose 3}2 x + O(x-1)$$ which evaluated at $x=1$ gives the desired answer.

This can be applied to get the result for higher powers, for example:
$$\sum_{k=1}^n k^3={n+1 \choose 2}+{n+1 \choose 3}6+{n+1 \choose 4}6$$

-
+1. I'm in love with this one! – Lyrebird Jul 3 '11 at 4:29
I must admit I didn't know this one even though the problem is quite popular. +1 – Patrick Da Silva Jul 10 '11 at 1:33
So slick I laughed reading this! – ttt Jul 10 '11 at 16:54
I waited in order to gain the commenting privilege just to say this : You made me fall in love with calculus again !! – Bouazza S. Jul 11 '11 at 2:10
@leonbloy Interesting! Will look at this tomorrow! – Pedro Tamaroff Mar 24 '12 at 6:48

I think it's useful to report here another proof that I have posted on Mathoverflow.

Write down numbers in an equilateral triangle as follows:

    1
2 2
3 3 3
4 4 4 4


Now, clearly the sum of the numbers in the triangle is $Q_n:=1^2+2^2+\dots+n^2$. On the other hand, if you superimpose three such triangles rotated by $120^\circ$ each, like these ones

    1          4          4
2 2        3 4        4 3
3 3 3      2 3 4      4 3 2
4 4 4 4    1 2 3 4    4 3 2 1


then the sum of the numbers in each position equals $2n+1$. Therefore, you can double-count $3Q_n=\frac{n(n+1)}{2}(2n+1)$. $\square$

The proof is not mine and I do not claim otherwise. I first heard it from János Pataki. It is similar (but simpler) to the proof appearing on Wikipedia as I am writing this.

How to prove formally that all positions sum to $2n+1$? Easy induction: moving down-left or down-right from the topmost number does not alter the sum, since one of the three summand increases and one decreases. This is a discrete analogue of the Euclidean geometry theorem "given a point $P$ in an equilateral triangle $ABC$, the sum of its three distances from the sides is constant" (proof: sum the areas of $APB,BPC,CPA$), which you can mention as well.

-
Nice, though I think the proof by Man-Keung Siu mentioned above is related. – ShreevatsaR Mar 19 '14 at 16:39

For proof by induction; these are the $\color{green}{\mathrm{three}}$ steps to carry out:

Step 1: Basis Case: For $i=1$: $$\sum^{i=k}_{i=1} i^2=\frac{1(1+1)(2\times 1+1)}{6}= \frac{2\times 3}{6}=1$$ So statement holds for $i=1$.

Step 2: Inductive Assumption: Assume statement is true for $i=k$:

$$\sum^{i=k}_{i=1} i^2=\frac{k(k+1)(2k+1)}{6}$$

Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$\sum^{i=k+1}_{i=1} i^2=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}$$

To do this you cannot use: $$\sum^{i=k}_{i=n} i^2=\color{red}{\frac{n(n+1)(2n+1)}{6}}$$ as this is what you are trying to prove.

So what you do instead is notice that: $$\sum^{i=k+1}_{i=1} i^2= \underbrace{\frac{k(k+1)(2k+1)}{6}}_{\text{sum of k terms}} + \underbrace{(k+1)^2}_{\text{(k+1)th term}}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{k(k+1)(2k+1)}{6}+\frac{6(k+1)^2}{6}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)\left(k(2k+1)+6(k+1)\right)}{6}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)(2k^2+\color{green}{7k}+6)}{6}=\frac{(k+1)(2k^2+\color{green}{4k+3k}+6)}{6}=\frac{(k+1)\left(2k(k+2)+3(k+2)\right)}{6}=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}\quad \forall \space k \in \mathbb{N}$$

Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $\color{blue}{\mathrm{blue}}$ equation at the end.

-

Another method:

\begin{align} \sum_{k=1}^nk^2&=\frac 12\sum_{k=1}^n k(k+1)+(k-1)k\\ &=\frac 12 \left[\sum_{k=1}^n k(k+1)+\sum_{k=1}^{n-1}k(k+1)\right]\\ &=\color{lightgrey}{\frac 12} \left[ \color{lightgrey}2\sum_{k=1}^n \binom {k+1}2+\color{lightgrey}2\sum_{k=1}^{n-1}\binom {k+1}2\right]\\ &=\binom {n+2}3+\binom {n+1}3\\ &=\frac{\color{blue}{(n+2)}(n+1)n}6+\frac{(n+1)n\color{blue}{(n-1)}}6\\ &=\frac {n(n+1)\color{blue}{(2n+1)}}6\quad\blacksquare \end{align}

-

My contribution: \begin{align} \sum_{k=1}^n k^2&=\frac 14\sum_{k=1}^n(2k)^2\\ &=\frac 14\sum_{k=1}^n\binom {2k}2+\binom {2k+1}2\\ &=\frac 14\sum_{k=2}^{2n+1} \binom k2\\ &=\frac 14\binom {2n+2}3\\ &=\frac 14\cdot \frac {(2n+2)(2n+1)(2n)}{1\cdot 2\cdot 3} =\color{lightgrey}{\frac{(n+1)(2n+1)n}{1\cdot 2\cdot 3}}\\ &=\frac 16n(n+1)(2n+1)\quad\blacksquare \end{align}

-
Why $\sum_{k=1}^n (2k)^2=\sum_{k=1}^n\left(\binom{2k}{2}+\binom{2k+1}{2}\right)$? – user236182 Oct 21 '15 at 17:19
@user236182 - For any integer $a$, $$a^2=\frac {a(a-1)}2+\frac {(a+1)a}2=\binom a2+\binom {a+1}2$$ Putting $a=2k$ gives the result used above. – hypergeometric Oct 21 '15 at 23:04
Why $\sum_{k=1}^{2n+1}\binom{k}{2}=\binom{2n+2}{3}$? – user236182 Oct 21 '15 at 23:07
@user236182 - The following is a well-known identity: $$\sum_{k=m}^N\binom km=\binom {N+1}{m+1}$$ A proof of it may be found here as a solution to a recent question. Putting $N=2n+1$ results in the identity used in the solution. – hypergeometric Oct 22 '15 at 14:42

\begin{align} x^{\underline{r}} = x (x - 1) \dotsm (x - r + 1) \end{align}

so that:

\begin{align} \Delta n^{\underline{r}} &= (n + 1)^{\underline{r}} - n^{\underline{r}} \\ &= r n^{\underline{r - 1}} \\ \sum_{0 \le k < n} k^{\underline{r}} &= \frac{n^{\underline{r + 1}}}{r + 1} \end{align}

(the last one is also easy to prove by induction, or otherwise).

Now note that:

\begin{align} n^2 = n^{\underline{2}} + n^{\underline{1}} \end{align}

so we can write:

\begin{align} \sum_{0 \le k \le n} k^2 &= \sum_{0 \le k < n + 1} \left( k^{\underline{2}} + k^{\underline{1}} \right) \\ &= \frac{(n + 1)^{\underline{3}}}{3} + \frac{(n + 1)^{\underline{2}}}{2} \\ &= \frac{(n + 1) n (n - 1)}{3} + \frac{(n + 1) n}{2} \\ &= \frac{(2 n + 1) (n + 1) n}{6} \end{align}

-

Another take, similar to Euler's (?) proof given by @leonbloy. We know that if:

\begin{align} A(z) &= \sum_{n \ge 0} a_n z^n \end{align}

then (writing $\mathtt{D}$ for the derivative):

\begin{align} z \mathtt{D} A(z) &= \sum_{n \ge 0} n a_n z^n \end{align}

Also:

\begin{align} \frac{A(z)}{1 - z} &= \sum_{n \ge 0} \left( \sum_{0 \le k \le n} a_n \right) z^n \\ \frac{1}{1 - z} &= \sum_{n \ge 0} z^n \end{align}

This you can repeat and combine. In our case, we get that:

\begin{align} \sum_{n \ge 0} n^2 &= (z \mathtt{D})^2 \frac{1}{1 - z} \\ &= \frac{z + z^2}{(1 - z)^3} \\ \sum_{n \ge 0} \left( \sum_{0 \le k \le n} k^2 \right) z^n &= \frac{z + z^2}{(1 - z)^4} \end{align}

We are interested in the coefficient of $z^n$:

\begin{align} [z^n] \frac{z + z^2}{(1 - z)^4} &= [z^n] \frac{z}{(1 - z)^4} + [z^n] \frac{z^2}{(1 - z)^4} \\ &= [z^{n - 1}] (1 - z)^{-4} + [z^{n - 2}] (1 - z)^{-4} \\ &= (-1)^{n - 1} \binom{-4}{n - 1} + (-1)^{n - 2} \binom{-4}{n - 2} \\ &= \binom{n - 1 + 4 - 1}{4 - 1} + \binom{n - 2 + 4 - 1}{4 - 1} \\ &= \binom{n + 2}{3} + \binom{n + 1}{3} \\ &= \frac{(n + 2) (n + 1) n}{3!} + \frac{(n + 1) n (n - 1)}{3!} \\ &= \frac{(2 n + 1) (n + 1) n}{6} \end{align}

This approach is less messy than the cited one (no horrible derivatives and then l'Hôpital thrice).

-
Its a bit awfully sophisticated for this fact but nice ^^ – Shadock Oct 21 '15 at 16:56

Here's one using the Pertubation Method I learnt in Concrete Mathematics: $$S_n = \sum_{0\leq j\leq n}j^3$$. $$S_n+(n+1)^3=\sum_{0\leq j\leq n+1}j^3$$ $$S_n+(n+1)^3=0+\sum_{1\leq j\leq n+1}j^3$$ Replacing $j$ by $j+1$ gives us $$S_n+(n+1)^3=\sum_{1\leq j+1 \leq n+1}(j+1)^3$$ Rewriting $1\leq j+1\leq n+1$ as $0\leq j\leq n$ and expanding$(j+1)^3$ $$S_n+(n+1)^3=\sum_{0\leq j \leq n}(j^3+1+3j^2+3j)$$ By Associative law $$S_n+(n+1)^3=\sum_{0\leq j \leq n}j^3 +\sum_{0\leq j\leq n}1 + 3\sum_{0\leq j \leq n}j^2+3\sum_{0\leq j\leq n}j$$ $S_n =\sum_{0\leq j\leq n}j^3$, so it gets canceled. Rewriting $\sum_{0\leq j\leq n}1$ and $\sum_{0\leq j\leq n}j$ as $(n+1)$ and $\frac{n(n+1)}{2}$ respectively $$(n+1)^3=(n+1)+\frac{3n(n+1)}{2}+3\sum_{0\leq j\leq n}j^2$$ $$3\sum_{0\leq j\leq n}j^2=(n+1)^3-\frac{3n(n+1)}{2} - (n+1)$$ $$3\sum_{0\leq j\leq n}j^2=(n+1)(n^2+1+2n-\frac{3n}{2}-1)$$ $$3\sum_{0\leq j\leq n}j^2=\frac{(n+1)(2n^2+n)}{2}$$ $$\sum_{0\leq j\leq n}j^2=\frac{n(n+1)(2n+1)}{6}$$ Using the same methods, one can get closed forms for even higher sums like $\sum_{j=0}^{n}j^3$ by taking $S_n = \sum_{0\leq j\leq n}j^4$ and using the binomial expansion for $(j+1)^4$

-

Another method by using telescoping sum :- We know $(a+b)^3-a^3-b^3=3ab(a+b)$ , take

$a=k-1 , b=2$ , then $a+b=k+1$ and $(k+1)^3-(k-1)^3-2^3=6(k-1)(k+1)=6k^2-6$ ,

hence $(k+1)^3-(k-1)^3-8+6=(k+1)^3-k^3+k^3-(k-1)^3-2=6k^2$ , taking sum over $k$

from $1$ to $n$ we get , $\sum_{k=1}^n [(k+1)^3-k^3] + \sum_{k=1}^n [k^3-(k-1)^3] -\sum_{k=1}^n 2 = 6 \sum_{k=1}^nk^2$ , the first

sum on the left hand side is telescoping resulting in $(n+1)^3-1$ , the second sum is also telescoping resulting in $n^3-(1-1)^3=n^3$ , and the third sum is simply $2n$ , hence

$6 \sum_{k=1}^nk^2=(n+1)^3-1+n^3-2n=2n^3+3n^2+n=n(n+1)(2n+1)$

-

Another simple proof could be as follows: note that each square can be written as a sum of odd numbers:

$\sum_{k=1}^n(2k-1)=n^2$.

(that can be easily shown)

When writing each square as a sum of odd numbers we get that

$S=\sum_{k=1}^n k^2=1 + (1+3) + (1+3+5) + ... =\sum_{k=1}^n(n-k+1)(2k-1)=$

$=(2n+3)\sum_{k=1}^n k -(n+1)\sum_{k=1}^n 1 -2S$.

Therefore

$3S=\frac{(2n+3)n(n+1)}{2}-n(n+1)=\frac{(2n+1)n(n+1)}{2}$.

-

A combinatorial proof:

Let $S=\{1,2,\dots,(n+1)\},n\ge 2$ and $T=\{(x,y,z)|x.y,z\in S,x< z,y< z\}$.By counting the number of members of $T$ in $2$ different ways I will prove the formula.

# $1$st way:

We will at first Choose $z$ form the set $S$.When $z$ is $1$ then there are no choices for $x,y$ so the no. of elements of $T$ with $z=0$ is zero.When $z=2$ the number of choices for $x$ is $1$ and so is for $y$(precisely $x=y=1$).When $z=3$ then $x\in \{1,2\}$ and $y\in \{1,2\}$ so total no. of choices equals $2^2$.In a similar manner when $z=k,(1\le k\le (n+1))$,no. of choices for $x$ equals $(k-1)$ and no. of choices for $y$ is also $(k-1)$. So total no . of elements of T with $z=k$ is $(k-1)^2$.

So we will get the total no. of elements of $T$ by summing $(k-1)^2$ up from $1$ to $(n+1)$.Hence $$|T|=\sum _{l=1}^{(n+1)}(l-1)^2=\sum_{k=1}^{n}k^2$$

# $2$nd way:

Among the elements of $T$ consisting of three numbers from the set $S$, there are elements in $x=y$ and elements in which $x\ne y$.

We can count the no. of elements in which $x=y$ by choosing two distinct nos. from $S$ and assigning $z$ with the lagest no. and $x,y$ with the smallest number. We can choose two distinct numbers from $S$ in $\displaystyle \binom{n+1}{2}$ ways, so the total no. elements having $x=y$ is $\displaystyle \binom{n+1}{2}$.

Now we have to count the number of elements in which $x\ne y$.This means that $x,y$ are dinstict and as they are less than $z$ this means that all the three are distinct. So we can count no. of such elements in $T$ in the following way.At first we will choose three elements from the set $S$ and assign the largest value to $z$ and assign the other two values to $x,y$. Now we can choose three numbers from the set $S$ in $\displaystyle \binom{n+1}{3}$.From each such three element we can get two elements of the set $T$(Assigning the largest to $z$ and then assigning any one of then to $x$ and the other to $y$). So no. of elements of $T$ having $x\ne y$ is $2\displaystyle \binom{n+1}{3}$

So by this method we have $|T|=\displaystyle \binom{n+1}{2}+2\displaystyle \binom{n+1}{3}$

On equating the result obtained from both the methods we have $$\sum_{k=1}^{n}k^2=\displaystyle \binom{n+1}{2}+2\displaystyle \binom{n+1}{3}=\frac{n(n+1)(2n+1)}{6}$$

Note that this can easily be extended to find the sum of $p$th power of integers.($p\in \mathbb{N})$

-

A probabilistic method that I learned from Jim Pitman's book Probability (exercise 3.3.10) is as follows. Let $X$ be uniformly distributed on the set $\{ 1, 2, \ldots, n \}$. Then $$E(X^3) = (1^3 + 2^3 + \ldots + n^3)/n$$ and $$E((X+1)^3) = (2^3 + 3^3 + \ldots +(n+1)^3)/n.$$ Subtracting the first of these from the second we get $$E((X+1)^3 - X^3) = ((n+1)^3 - 1)/n$$ and we can simplify both sides a bit to get $$E(3X^2 + 3X + 1) = n^2 + 3n + 3.$$ By linearity of expectation we can expand the left-hand side to get $$3 E(X^2) + 3 E(X) + 1 = n^2 + 3n + 3.$$

Now $E(X) = (1+2+\ldots+n)/n = (n+1)/2$. Substituting this in and solving for $E(X^2)$ gives

$$E(X^2) = {(n+1)(2n+1) \over 6}$$ but of course $E(X^2) = (1^2+2^2+\cdots +n^2)/n$.

Similarly, we can derive for each $k$ $$\sum_{j=0}^{k-1} {k \choose j} E(X^j) = \sum_{l=1}^k {k \choose l} n^{l-1}$$ and so if we know $E(X^0), \ldots, E(X^{k-2})$ we can solve for $E(X^{k-1})$. So this method generalizes to higher moments as well.

-
never seen such a demonstration like this, thanks!!! – d555 Apr 25 '12 at 6:11
I was rather surprised when I saw this for the first time as well. – Michael Lugo Apr 25 '12 at 16:32
Nice, needs more up votes. – k.stm May 28 '13 at 7:13

\begin{aligned} & \hspace{0.5in} \begin{aligned}\displaystyle \sum_{1 \le k \le n}k^2 & = \sum_{1 \le k \le n}~\sum_{1 \le r \le k}r =\sum_{1 \le r \le n}~\sum_{r \le k \le n}r \\& = \sum_{1 \le r \le n}~\sum_{1 \le k \le n}r-\sum_{1 \le r \le n}~\sum_{1 \le k \le r-1}r \\& = n\sum_{1 \le r \le n}r-\frac{1}{2}\sum_{1 \le r \le n}r(r-1) \\& =\frac{1}{2}n^2(n+1)-\frac{1}{2}\sum_{1 \le r \le n}r^2+\frac{1}{2}\sum_{1 \le r \le n}r \\& =\frac{1}{2}n^2(n+1)-\frac{1}{2}\sum_{1 \le k \le n}k^2+\frac{1}{4}n(n+1) \end{aligned} \\& \begin{aligned}\implies\frac{3}{2}\sum_{1 \le k \le n}k^2 & = \frac{1}{2}n^2(n+1)+\frac{1}{4}n(n+1) \\& = \frac{1}{4}n(n+1)(2n+1) \end{aligned}\\& \implies \hspace{0.15in} \displaystyle \sum_{1 \le k \le n}k^2 = \frac{1}{6}n(n+1)(2n+1).\end{aligned}

-
This is an approach that I like. It can be generalized to \begin{align}f(n, m) &= \sum_{k = 1}^n k^m \\&= \sum_{k = 1}^n \sum_{r = 1}^k k^{m-1} \\&= \sum_{1 \le r \le k \le n} k^{m-1} \\&= \sum_{r = 1}^n \sum_{k=r}^n k^{m-1} \\&= \sum_{r=1}^n f(n, m-1 ) - f(r - 1 , m - 1) \end{align} to be able to recursively solve any case. – DanielV Jan 11 at 13:50

The sum of the first n k-th powers (among other things) is given by Gauss's Summation Formula. No guessing is necessary. You just turn the crank.

Justification for this assertion can be found at the following link: Summation formula name

Edit: Perhaps instead of offering this as an answer, I should have made it just a comment.

-
The only "Gauss summation formula" a google search turns up is the formula $$\sum_{k=1}^nk=\frac{n(n+1)}{2}$$ which is not relevant to the OP's question and does not do what you said. The sum of the first $n$ $k$th powers is a complicated expression involving Bernoulli numbers. Also, I'm not sure what "guessing" you are referring to. Please improve your answer. – Zev Chonoles Jun 28 '11 at 5:19
@Zev Chonoles: So you think everything of value has been loaded onto the web? You have the faith of a Breton peasant. Anyway, the Bernoulli numbers are implicit in the formula that I cited, and I added a link giving the justification of the formula. – Mike Jones Jul 12 '11 at 20:19
Where did I ever say I thought "everything of value has been loaded onto the web"? Since you had explained nothing about the mathematics of the claim in your answer, there was nothing to go on other than the words "Gauss's summation formula". It's not the internet's fault you were using a non-standard name for this formula. And I don't know what the faith of a Breton peasant is supposed to be like (this quote makes no sense to me), but I don't think I appreciate your implication, whatever it is. – Zev Chonoles Jul 12 '11 at 20:51
Obviously, I have no control over the voting decisions of others, so I have no clue what it is you're complaining to me about. Furthermore, in my opinion people should choose how to vote on a post independently of what its current total score is; there is no such thing as an "appropriate" total score for a post. If three people came across your post and independently decided that it was not sufficiently useful, then a total score of -3 is the result. – Zev Chonoles Jul 14 '11 at 5:03
While the idea behind your post is quite interesting, I still find the post itself unhelpful because you have not provided a worked example of the sum of $k$th powers being derived from the Euler-Maclaurin formula. If you added this, I would be happy to replace my downvote with an upvote - I cannot speak for anyone else. – Zev Chonoles Jul 14 '11 at 5:06

This is a method that I learned from Polya's Mathematics and Plausible Reasoning: Let $s(n) = 1 + 2 + \cdots + n$ and let $t(n) = 1^2 + 2^2 + \cdots + n^2$. Make a small table as follows:

   n = 1 2  3  4  5
t(n) = 1 5 14 30 55
s(n) = 1 3  6 10 15


Note the ratio $r(n) = t(n)/s(n)$ for sucessive values of $n$:

R(1) = 1 = 3/3
R(2) = 5/3
R(3) = 14/6 = 7/3
R(4) = 30/10 = 3 = 9/3
R(5) = 55/15 = 11/3


Based on the pattern it seems that $r(n) = (2n+1)/3$ (and in fact it is: just prove it by induction). It follows that $t(n) = r(n)s(n)$. Now use the fact that $s(n) = n(n+1)/2$.

-

Sums of polynomials can be done completely mechanically (no insight required, just turn the handle!) using the discrete calculus. Bill Dubuque mentions this in his answer, but I think it's nice to see a worked example.

Represent $k^2$ in terms of falling powers (easy by inspection in this case, but you can use Stirling subset numbers to convert): $$k^2 = k^{\underline 2} + k^{\underline 1}$$

Sums of falling powers are easy, just like integration of ordinary powers, except for the treatment of limits: $$\sum_{k=1}^n k^{\underline 2} + k^{\underline 1} = \bigg({1\over 3}k^{\underline 3} + {1\over 2}k^{\underline 2}\bigg)\ \bigg|^{n+1}_0$$

And then convert back into ordinary powers (by expansion, or using signed Stirling cycle numbers): $${1\over 3}((n+1)^3 - 3(n+1)^2 + 2(n+1)) + {1\over 2}((n+1)^2 - (n+1))$$

And then you can rearrange to get the answer you want.

-

Proof 1. (Exercise 2.5.1 in Dias Agudo, Cândido da Silva, Matemáticas Gerais III). Let $S:=\sum_{k=1}^{n}k^{2}$. Consider $(1+a)^{3}=1+3a+3a^{2}+a^{3}$ and sum $(1+a)^{3}$ for $a=1,2,\ldots ,n$:

$$\begin{eqnarray*} (1+1)^{3} &=&1+3\cdot 1+3\cdot 1^{2}+1^{3} \\ (1+2)^{3} &=&1+3\cdot 2+3\cdot 2^{2}+2^{3} \\ (1+3)^{3} &=&1+3\cdot 3+3\cdot 3^{2}+3^{3} \\ &&\cdots \\ (1+n)^{3} &=&1+3\cdot n+3\cdot n^{2}+n^{3} \end{eqnarray*}$$

The term $(1+1)^3$ on the LHs of the 1st sum cancels the term $2^3$ on the RHS of the 2nd, $(1+2)^3$, the $3^3$, $(1+3)^4$, the $4^3$, ..., and $(1+n-1)^3$ cancels $n^3$. Hence

$$(1+n)^{3}=n+3\left( 1+2+\ldots +n\right) +3S+1$$

and

$$S=\frac{n(n+1)(2n+1)}{6},$$

because $1+2+\ldots +n=\dfrac{n\left( n+1\right) }{2}$.

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

-

A natural approach for this kind of problems when you don't know the result is to proceed as follows :

We may want to write the sum $\sum_{k=1}^n k^2$ as a telescopic sum, so we will try to find a polynomial of degree 3 ( why ? ) $P$ so that $P\left( k+1 \right) - P\left(k\right)=k^2$. Let $P\left( x \right) = ax^3+bx^2+cx$ for all reals $x$, then our constraint becomes :

$k^2= a\left( \left(k+1\right)^3 - k^3 \right) + b\left( \left(k+1\right)^2 - k^2 \right) + c$

Which after expanding and rearranging becomes :

$k^2 = 3ak^2 + \left( 3a+2b \right)k + a+b+c$

But we know that two polynomials are equal iff their coefficients are equal too, so we just need to solve this system :

\left\{ \begin{aligned} a &= \frac{1}{3} \\ 3a+2b &= 0 \\ a+b+c &= 0 \end{aligned} \right.

Which gives us $\left( a,b,c \right) = \left( \frac{1}{3}, \frac{-1}{2}, \frac{1}{6} \right)$

And Voilà, we just found the coefficients of our polynomial ! Now we just have to evaluate our telescopic sum :

$\sum_{k=1}^n k^2 = \sum_{k=1}^n P\left( k+1 \right) - P\left(k\right) = P\left(n+1\right)-\underbrace{P\left(1\right)}_{=0}$

$\sum_{k=1}^n k^2 = \frac{1}{3}\left(n+1\right)^3 - \frac{1}{2}\left(n+1\right)^2+\frac{1}{6}\left(n+1\right)$

$\sum_{k=1}^n k^2 = \frac{1}{6}\left(n+1\right)\left( 2 \left(n+1\right)^2 - 3 \left(n+1 \right) + 1 \right)$

$\sum_{k=1}^n k^2 = \frac{1}{6}\left(n+1\right)\left( 2n^2+n \right)$

$\sum_{k=1}^n k^2 = \frac{1}{6}n\left(n+1\right)\left(2n+1\right)$

Which completes the proof :-)

-

Yet another proof(!)

Notice that $(k+1)^3 - k^3 = 3k^2 + 3k + 1$ and hence

$$(n+1)^3 = \sum_{k=0}^n \left[ (k+1)^3 - k^3\right] = 3\sum_{k=0}^n k^2 + 3\sum_{k=0}^n k + \sum_{k=0}^n 1$$

which gives you

\begin{align} \sum_{k=1}^n k^2 & = \frac{1}{3}(n+1)^3 - \frac{1}{2}n(n+1) - \frac{1}{3}(n+1) \\ & = \frac{1}{6}(n+1) \left[ 2(n+1)^2 - 3n - 2\right] \\ & = \frac{1}{6}(n+1)(2n^2 +n) \\ & = \frac{1}{6}n(n+1)(2n+1) \end{align}

-
$(n+1)^3 = \sum_{k=0}^n (k+1)^3 - k^3$ ? $(n+1)^3 = \sum_{k=0}^n (k+1)^3 - \sum_{k=0}^n k^3$ – Tao Hacker Jun 28 '11 at 8:28
I added some brackets; better? – Chris Taylor Jun 28 '11 at 9:25
OK. I understand now. – Tao Hacker Jun 28 '11 at 12:35
The appeal of this proof is that it's sort of the discrete counterpart to the integral: $\int_0^n x^2 dx= n^3/3$ – leonbloy Jan 14 '13 at 19:35

I like this visual proof, due to Man-Keung Siu. It appeared in the March 1984 issue of Mathematics Magazine.

See also two more proofs (as well as this one) in Roger Nelson's Proofs Without Words: Exercises in Visual Thinking.

-
In a similar vein are most posts in this MO-thread. Incidentally, another Mike posted Man-Keung Siu's proof there. – t.b. Jun 28 '11 at 5:21
Beautiful extension of the classic Gauss sum proof - I love this one! – Steven Stadnicki Oct 28 '11 at 22:20

Another way to prove this by induction goes as follows:

Base case: If $n=0$, then we have $0$ on the left hand side, and $0(0+1)(2(0)+1)/6=0$ on the right.

Induction step:

Consider the differences $L(j+1)-L(j)$, and $R(j+1)-R(j)$ where $L(j)$ indicates that we have $j$ for $n$ on the left hand side. Well, $L(j+1)-L(j)=(j+1)^2$, and $$R(j+1)-R(j)=\frac{(j+1)((j+1)+1))(2(j+1)+1)}{6} - \frac{j(j+1)(2j+1)}{6}$$ which simplifies to $(j+1)^2$ also. So, the rates of change on both sides equal each other, and thus the induction step follows.

-

To verify the identity, note $\rm\:\sum_{k=1}^n\: k^2 = f(n)\ \iff\ f(n+1) - f(n) = (n+1)^2\:$ and $\rm\: f(1) = 1\:.$ But it's rote polynomial arithmetic to check that the RHS polynomial satisfies this recurrence.

To discover the identity, notice that any polynomial solution of the above recurrence has degree at most $3$. Hence it's easy to find the polynomial solution by substituting a cubic polynomial with undetermined coefficients.

Generally one can give a formula for sums of power using Bernoulli polynomials (motivated by discrete analogs of integrals of powers). The general theory becomes much clearer when one studies finite difference calculus and umbral calculus.

-

The standard method is induction and you should look it up as it is a popular second example (first is $\sum n$)

Another argument is use: $$24n^2 +2= (2n+1)^3-(2n-1)^3$$ and get a telescoping sum.

i.e $$24\sum_1^n k^2 +2n = \sum_1^n (2k+1)^3-\sum_1^n (2k-1)^3$$ $$24\sum_1^n k^2 +2n = (2n+1)^3-1$$ $$24\sum_1^n k^2 =8 n^3+12 n^2+4 n$$ $$24\sum_1^n k^2 =4 n (n+1) (2 n+1)$$ $$\sum_1^n k^2 = \frac{n (n+1) (2 n+1)}{6}$$

-
For a combinatorial argument see Sivaram's answer here – kuch nahi Jun 27 '11 at 23:23

Proof (by induction)

Basis: Check it for n = 1 (it works out).

Induction: Assume the result is true for a given value of $n$. That is, assume $$\sum_{k = 1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.$$ Try to show that the result holds for $n+1$. \begin{align*} \sum_{k = 1}^{n+1} k^2 &= \sum_{k=1}^n k^2 + (n+1)^2\\ &= \frac{n(n+1)(2n+1)}{6} + (n+1)^2\\ &= \frac{n(n+1)(2n+1) + 6(n+1)^2}{6}\\ &= \frac{(n+1)(n+1+1)(2(n+1)+1)}{6}. \end{align*}

-