Counting the number of squares on an $n\times n$ Board Yesterday I was asked by a friend how many squares are in a chess board of $8\times 8$.
I thought about 64 immediately, but of course this is not the solution, there are much more.
So the number of squares is: $$8\times 8 + 7\times 7 + 6\times 6 + 5\times 5 + 4\times 4 + 3\times 3 + 2\times 2 + 1\times 1=1^2 + 2^2 + 3^2 + 4^2...+ 8^2$$
I came across this formula: $$\frac{n(n + 1)(2n + 1)} 6$$
It produces the sum of squares in $n\times n$ board.
My question is, how did he reached this formula? Did he just guessed patterns until he reached a match, or there is a mathematical process behind?
If there is a mathematical process, can you please explain line by line?
Thanks very much.
Btw: Couldn't find matching tags for this question, says I can't create.

The first step is to recognize that there are $8^2$ squares of size $1$ by $1$, $7^2$ squares of size $2$ by $2$ and so on.  That justifies the total number being, as you say, $1^2+2^2+3^2+\ldots 8^2$.  Sums of powers are calculated by Faulhaber's formula.  There are several ways to derive them.  One way is to know or suspect that $\sum_{k=1}^n k^p$ should be of degree $p+1$.  So for squares, we want $\sum_{k=1}^n k^2=an^3+bn^2+cn+d$.  Then if we evaluate it at $n+1$, we get $\sum_{k=1}^{n+1} k^2=a(n+1)^3+b(n+1)^2+c(n+1)+d$.  Subtracting, we get $(n+1)^2=a((n+1)^3-n^3)+b((n+1)^2-n^2)+c((n+1)^1-n^1)$ and equating the coefficients gets the desired formula.  You can prove the formula rigorously by induction
