3
$\begingroup$

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$
3
  • $\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$ 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$ 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
9
$\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, the result of the subtraction, $s_{2,n+1,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+(a+1)^M-n^{M}-(n-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$
4
  • $\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
9
$\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$
1
  • $\begingroup$ I like this way, intuitive (for me). $\endgroup$ Oct 3 at 0:45
5
$\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.