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

Question

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?

Answer 1

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

Answer 2

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

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

Deriving 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}$$

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

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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

Answer 11

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 :-)

Answer 12

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.

Answer 13

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.

Answer 14

$\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}$

Answer 15

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.