1
$\begingroup$

This question already has an answer here:

I was going over the problem of finding the number of squares in a chessboard, and got the idea that it might be the sum of squares from $1$ to $n$. Then I searched on the internet on how to calculate the sum of squares easily and found the below equation:$$\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6}.$$

And then I searched for an idea on how to come up with this equation and found this link, but what I would like to know is that if (hypothetically)I have to be the first person in the world to come up with this equation, then can someone please tell some ideas on how to approach a problem like this.

$\endgroup$

marked as duplicate by Grigory M, Davide Giraudo, Namaste discrete-mathematics Jun 1 '14 at 12:18

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$ Possibly try integration of some kind? There seems to be a sort of relationship between the order of the formula and the highest order term in the summation. $\endgroup$ – FundThmCalculus Jun 1 '14 at 10:26
  • $\begingroup$ What is "number of squares in a chessboard"? There are 64 black and white squares on a chess board. Do you need to find out in how many ways you can combine them into larger composite squares? $\endgroup$ – LutzL Jun 1 '14 at 11:13
  • $\begingroup$ @anirudh A good way to recursively derive a formula for $\sum_{i=1}^n i^M$ is to look at $\sum_{i=1}^n (i+a)^M$ and apply the binomial theorem, which lets you write $(i+a)^M$ in terms of $i^k$, for $0\le k\le M$. You may see my updated answer. $\endgroup$ – mathse Jun 1 '14 at 17:45
7
$\begingroup$

Actually, the answer in your link confused me a bit. But here is an alternative derivation (somehow similar to/same as? the answer in your link).

Look at the sequence of cubes $s_{1,n,3}=1^3+2^3+\cdots+n^3$ and the shifted sequence $s_{2,n+1,3}=2^3+\cdots+(n+1)^3$. Subtracting the former sequence from the latter obviously yields $(n+1)^3-1$. At the same time $s_{2,n,3}-s_{1,n,3}$ is given by

$$ \sum_{i=1}^n \left((i+1)^3-i^3\right) = \sum_{i=1}^n \left(3i^2+3i+1\right)=3s_{1,n,2}+3s_{1,n,1}+n.$$

In other words,

$$(n+1)^3-1=s_{2,n,3}-s_{1,n,3}=3s_{1,n,2}+3s_{1,n,1}+n.$$

Assuming that you know that $s_{1,n,1}=\sum_{i=1}^n i= \frac{n(n+1)}{2}$ you can solve for $s_{1,n,2}=\sum_{i=1}^n i^2$, which is what you have been looking for.

EDIT This can be generalized as follows (and this maybe gives a better motivation).

Suppose we wish to compute $\sum_{i=1}^n i^M$ for some positive integer $M$, and we want to find a recursive formula that expresses $\sum_{i=1}^n i^M$ in terms of $\sum_{i=1}^n i^{M-1}$, $\sum_{i=1}^n i^{M-2}$, etc.

The key idea is to look at the sum $S=\sum_{i=1}^n (i+a)^M$, for some positive integer $a$. By the binomial theorem, $(i+a)^M=\sum_{k=0}^{M}\binom{M}{k}i^ka^{M-k}$, so

$$\sum_{i=1}^n (i+a)^M=S=\sum_{k=0}^{M}\Bigl(\binom{M}{k}a^{M-k}\sum_{i=1}^n i^k\Bigr)=\binom{M}{0}a^M\sum_{i=1}^n i^0+\cdots+\binom{M}{M}a^0\sum_{i=1}^n i^{M}.$$

Conversely, notice how $S$ is just the 'right-shifted' (by $a$) analogue of $\sum_{i=1}^n i^{M}$; thus $$\sum_{i=1}^n (i+a)^M-\sum_{i=1}^n i^M=\underbrace{(n+a)^M+(n+a-1)^M+\cdots+(n+1)^M-a^{M}-(a-1)^{M}-\cdots-1^M}_{=B}.$$

In other words,

$$\sum_{k=0}^{M-1}\Bigl(\binom{M}{k}a^{M-k}\sum_{i=1}^n i^k\Bigr)=S-\sum_{i=1}^n i^M=B$$

and this allows us to write any sum of the form $\sum_{i=1}^n i^k$ in terms of the 'remaining' sums $\sum_{i=1}^n i^q$, for $q\neq k$. In particular, we may obtain an induction formula.

$\endgroup$
  • $\begingroup$ This does not answer the question of how to come up with this formula. $\endgroup$ – user133281 Jun 1 '14 at 12:00
  • $\begingroup$ Why does it not? It even answers how to come up with a formula for $\sum_{i=1}^n i^5$? $\endgroup$ – mathse Jun 1 '14 at 12:00
  • $\begingroup$ Of course the proof is correct; but to look at the sum of cubes instead of squares might feel a bit unmotivated. $\endgroup$ – user133281 Jun 1 '14 at 12:02
  • $\begingroup$ @user133281 See my updated edit part. Maybe you find this better motivated. $\endgroup$ – mathse Jun 1 '14 at 17:19
7
$\begingroup$

You might say, "When I sum up $ 1 + 1 + 1 + \ldots 1$ $n$ times I get $n$. So the sum of the $0$th powers is linear in $n$.

"When I sum up $1 + 2 + \ldots + n$, I get $n(n+1)/2$, so the sum of first powers is quadratic in $n$.

"So maybe the sum of squares is cubic in $n$. So I'm looking for a cubic function $p$ such that $$ p(n+1) - p(n) = (n+1)^2, $$ for every $n$. Writing that out, it's $$ a(n+1)^3 + b (n+1)^2 + c(n+1) + d - ( a n^3 + b n^2 + cn + d) = (n+1)^2." $$ That's an equality between two cubics, so their coefficients must be pairwise equal; you can solve for $a, b, c, d$. When you do, you get an answer, and the only question is "Is this in fact a correct answer to the original question?" You can verify that it is a correct answer by doing a proof by induction.

Bernouilli (maybe?), in Ars Conjectandi, did this for sums of squares, cubes, etc., up to 9th or 10th powers, and then claimed that the pattern of coefficients was easily discerned. I learned this from Spivak's wonderful book Calculus back in 11th grade.

$\endgroup$
3
$\begingroup$

Set $S = \sum_{i=1}^{\infty}i^2$, and noting that

\begin{align} S = 1^2 + 2^2 + \ldots + (n-1)^2 + n^2 \\ = 1 + 2 + 3 + \ldots + (n-1) + n \\ +2 + 3 + \ldots + (n-1) + n \\ +3 + \ldots + (n-1) + n \\ \ldots\\ (n-1) + n \\ + n \end{align}

Where there are n lines in that second sum. From this we get

\begin{align} S &= \sum_{i=1}^n\sum_{j=i}^nj \\ &= \sum_{i=1}^n\frac{(-i + n+1)(i+n)}{2} \\ &= \sum_{i=1}^n (\frac i2 - \frac{i^2}{2} + \frac{n}{2} + \frac{n^2}{2}) \\ &= \frac{n^2}{2} + \frac{n^3}{2} + \frac{1}{2}\sum_{i=0}^{n}i - \frac{1}{2}\sum_{i=1}^{n}i^2 \\ &= \frac{n^2}{2} + \frac{n^3}{2} + \frac{n(1+n)}{4} - \frac{S}{2} \end{align}

Moving the $S$ to the LHS and simplifying gives the equation you're looking for. \begin{align} S = \frac{(n^2 + n)(2n+1)}{6} \end{align}

$\endgroup$

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