How do I derive the formula for the sum of squares? [duplicate]

Question

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.

Answer 1

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.

Answer 2

Set $S = \sum_{i=1}^{n}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\left(\sum_{j=1}^nj - \sum_{j=1}^{i-1}j\right)\\ &= \sum_{i=1}^n\left(\frac{n(n+1)}{2} - \frac{i(i-1)}{2}\right)\\ &= \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}

Answer 3

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.