Intuition behind the formula for $\sum i^{2}$

Question

I've been trying to figure out the intuition behind the closed formula:

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

This is not hard to prove via induction, so I'm not interested in the proof that this is true. Rather, I'm more interested in why somebody would even make this guess for an inductive step. What's so confusing to me is that $\sum i = \frac{(n)(n+1)}{2}$ makes sense using the Gaussian trick of taking the number line and folding it in half and realizing that $(1+n) = (2+(n-1)) = (3 +(n-2)) ... $ so that you end up with this form.

But, what's the intuition for $i^{2}$? Looking at these two formulas, one realizes very quickly that

$$\sum i^{2} = \sum i * \frac{(2n+2)}{3}$$

But, why is that true intuitively? What's the intuition for this?

Answer 1

Since you asked for an intuitive explanation consider a simple case of $1^2+2^2+3^2+4^2$ using a set of children's blocks to build a pyramid-like structure.

First you arrange $16$ blocks in a $4\times4$ square. Next you place on top of this arrangement, $9$ blocks in a $3\times3$ square aligning the blocks of the upper left corner of each square, one above the other. On top of this construction place $4$ blocks in a $2\times2$ square, similarly aligned. Finally crown the upper left corner with a single block for the $1\times1$ square.

The following table represents the number of block in each column of the arrangement viewed from above:

$\begin{array}{cccc} 4&3&2&1\\ 3&3&2&1\\ 2&2&2&1\\ 1&1&1&1 \end{array}$

We can find the total number of blocks in the arrangement by adding the number of columns containing a single block to twice the number of columns containing two blocks then adding three times the number of columns containing three blocks and finally adding four times the one column containing four blocks.

\begin{eqnarray} \sum_{i=1}^4i^2=1\cdot(4+3)+2\cdot(3+2)+3\cdot(2+1)+4\cdot1 \end{eqnarray}

If we do the same thing with a pyramid of blocks having $n\times n$ blocks on its base then the summation would look like the following:

\begin{eqnarray} \sum_{i=1}^{n}i^2&=&1\cdot(n+n-1)+2\cdot(n-1+n-2)+3\cdot(n-2+n-3)\\ &+&\cdots+(n-1)\cdot(2+1)+n\cdot1\\ &=&1\cdot(2n-1)+2\cdot(2n-3)+3\cdot(2n-5)+\cdots+(n-1)\cdot3+n\cdot1\\ &=&\sum_{i=1}^{n}i(2n-2i+1)\\ &=&2n\sum_{i=1}^{n}i-2\sum_{i=1}^{n}i^2+\sum_{i=1}^{n}i\\ \sum_{i=1}^{n}i^2&=&(2n+1)\sum_{i=1}^{n}i-2\sum_{i=1}^{n}i^2\\ 3\sum_{i=1}^{n}i^2&=&(2n+1)\sum_{i=1}^{n}i\\ &=&\dfrac{n(n+1)(2n+1)}{2}\\ \sum_{i=1}^{n}i^2&=&\dfrac{n(n+1)(2n+1)}{6} \end{eqnarray}

Answer 2

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

_{(source: scienceblogs.de)}

Note that I've obtained this from this Mathoverflow question. The original author is Man-Keung Siu.

Answer 3

There is this really cool thing called Pascal's triangle. Perhaps you've heard of it, and it is shown below;

You may also know of the Hockey Stick Identity:

Amazingly, the Hockey Stick Identity can be used to almost directly show that

$$\sum_{k=1}^nk(k+1)(k+2)\dots (k+p)=\frac{n (n+1)(n+2)\dots (n+p+1)}{p+2} $$

See then that if $p=1,0$, we have

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

I like to use this because the general sum involving $p$ can be derived as a combination sum by dividing both sides by $(p+1)!$. It also happens to be easy to remember and generally works well for deriving formulas for $\sum k^a$. Just to show how it would work for $k^3$,

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

Answer 4

Taking differences once give $i^2$, again gives $2i-1$, and a third time gives a constant $2$.

This suggests the formula should be a third-degree polynomial with leading coefficient $\dfrac{2}{3!}=\dfrac13$ as you might expect if you integrate $2$ three times.

It is then not difficult to find the solution: one way is to look at $\sum i^{2} - \dfrac{n^3}{3}$ and take its first and second difference to get a constant. In the end this will give an inductive hypothesis of $$\sum_{i=1}^n i^{2}=\dfrac{n(n+1)(2n+1)}{6}$$ which is a typo away from your question