algebra precalculus - Counting the number of squares on an $ntimes 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.

Answer

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