sequences and series - How do I derive the formula for the sum of squares?

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

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.