0
$\begingroup$

This question already has an answer here:

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Are you familiar with induction? $\endgroup$ – Brent Mar 6 '15 at 2:54
  • $\begingroup$ 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. $\endgroup$ – user220080 Mar 6 '15 at 3:16
  • $\begingroup$ @user85503 displaystyle isn't appropriate for titles. $\endgroup$ – dustin Mar 6 '15 at 3:17
2
$\begingroup$

You want the number of squares in the following image:

enter image description here

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.

The final answer is thus:

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

$\endgroup$
  • $\begingroup$ 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 :/ $\endgroup$ – user220080 Mar 6 '15 at 3:08
1
$\begingroup$

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.