<s>[INST] 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.
 [/INST] 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}
</s>