6
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ Do any of these answers work for you? $\endgroup$ – Najib Idrissi Nov 25 '16 at 17:18
  • $\begingroup$ Have you already checked en.wikipedia.org/wiki/Square_pyramidal_number? $\endgroup$ – user302982 Nov 25 '16 at 17:18
  • $\begingroup$ This blog post might also be helpful. $\endgroup$ – user137731 Nov 25 '16 at 17:20
  • $\begingroup$ Early college my first intuitions were like: Integral of i is like i^2/2! .. Since i not starting with 0 more accurately i(i+1)/2; similarly integral of i^2 is like i^3 /3! or i(i+1) (i+i+1)/3!; Integral of i^3 = i^4/4 = (i^2/2!)^2 = etc :)) $\endgroup$ – Narasimham Nov 25 '16 at 17:35
  • 4
    $\begingroup$ Your formula is not correct. It should be $\frac {n(n+1)\color{red}{(2n+1)}}6$. $\endgroup$ – hypergeometric Nov 25 '16 at 17:43
7
$\begingroup$

Since you asked for an intuitive explanation consider a simple case of $1^2+2^2+3^4+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}

$\endgroup$
2
$\begingroup$

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

enter image description here

You may also know of the Hockey Stick Identity:

enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ Then look up the Stirling numbers. $\endgroup$ – marty cohen Nov 25 '16 at 18:43
  • $\begingroup$ @MartyCohen Becoming more and more combinatorial? Not sure how OP would take that. $\endgroup$ – Simply Beautiful Art Nov 25 '16 at 18:46
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

alt text
(source: scienceblogs.de)

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

$\endgroup$
  • $\begingroup$ That MO post has wonderful material. $\endgroup$ – Simply Beautiful Art Nov 25 '16 at 23:51

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.