# Having trouble understanding why $\sum_{i=1}^ni^2= \frac{n(n+1)(2n+1)}{6}$ [duplicate]

So I understand $\sum\limits_{i=1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$ but I'm not sure how to come to that conclusion. Having trouble understanding

## marked as duplicate by dustin, user147263, Jonas Meyer, Adam Hughes, SpencerMar 6 '15 at 4:32

• Are you familiar with induction? – Brent Mar 6 '15 at 2:54
• There was actually a question about this exact identity about a week ago and two good answers were given: one that showed how to write the proof up very nicely and another with a different approach. Maybe you will find that to be of use. – user220080 Mar 6 '15 at 3:16
• @user85503 displaystyle isn't appropriate for titles. – dustin Mar 6 '15 at 3:17

You want the number of squares in the following image:

If you assign three coordinates $(a,b,c)$ to each of the small squares. Where $a$ tells you the big square to which the small square belongs, $b$ gives you the horizontal position of the small square within the big square and $c$ gives you the vertical position of the small square within the big square, what you want to count is the number of triples $(a,b,c)$ with $n\geq a\geq b,c$. Separate into three to count:

There are $2\binom{n}{3}$ where all entries are different.

There are $3\binom{n}{2}$ where $2$ entries are equal and two different.

There are $n$ where all entries are equal.

$2\binom{n}{3}+3\binom{n}{2}+n=\frac{2n(n-1)(n-2)}{6}+\frac{3n(n-1)}{2}+n=\frac{n(n+1)(2n+1)}{6}$

This method can be used to find the sum of the $n$'th powers, but you need to compute stirling coefficients and it can get messy. Although it should be straightforward to see how we can prove from here that the formula is always going to be a polynomial of degree $n+1$

• Hmm. Maybe the question shouldn't be marked as a duplicate simply because of a nicer/different answer than what most would give (presumably a very simple inductive argument). I'm sure it will be sent off to duplicate land anyway though :/ – user220080 Mar 6 '15 at 3:08

Usually in early proof classes, you're given the formula and are expected to prove it with induction. Actually finding what the formula is turns out to be a harder task. It seems that you would like to know how to do this, so here's a way. Begin with this equation:

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

This works because the sum telescopes. Now binomial expand the $(i-1)^k$. After some cancellation and reordering of terms, you get

$$n^k=\sum_{j=1}^{k} {k \choose j} (-1)^{j+1} \sum_{i=1}^n i^{k-j}.$$

If we isolate the $j=1$ term, we get

$$n^k=k \sum_{i=1}^n i^{k-1} + \sum_{j=2}^k {k \choose j} (-1)^{j+1} \sum_{i=1}^n i^{k-j}.$$

Now we can solve this for $\sum_{i=1}^n i^{k-1}$. We find

$$\sum_{i=1}^n i^{k-1} = \frac{n^k + \sum_{j=2}^k {k \choose j} (-1)^j \sum_{i=1}^n i^{k-j}}{k}.$$

Rewriting, let $S(n,k)=\sum_{i=1}^n i^k$. Then we have

$$S(n,k-1)=\frac{n^k + \sum_{j=2}^k {k \choose j} (-1)^j S(n,k-j)}{k}.$$

Now you can start the recursion with the simple fact that $S(n,0)=n$. For example

$$S(n,1)=\frac{n^2+\sum_{j=2}^2 {2 \choose j} (-1)^j S(n,2-j)}{2} = \frac{n^2+n}{2}.$$

• Well Done, Ian! That is a very straightforward methodology! – Mark Viola Mar 6 '15 at 3:45