# 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.

-

## 2 Answers

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

-
You should say, "So for squares, $p=2$, ..." and then later you have $k^{n+1} = ...$ when you mean $k^2 = ...$ – Thomas Andrews Apr 12 '12 at 15:30
@ThomasAndrews: Thanks. Fixed. For the second it should have been $(n+1)^2$ as that is the term added to the sum. – Ross Millikan Apr 12 '12 at 15:55
Oops my bad, had a mistake, ignore please. Thanks for the help Ross! – Novak Apr 12 '12 at 21:09
I accidently marked this as solved, even though I believe your answer is correct. I'm in the stage of the substracting. Can you please write the stages after? All of these techniques are new to me, as I'm only in the 10th grade. What am I supposed to do with the coefficients? Thanks – Novak Apr 13 '12 at 16:11
@GuyDavid: If you take the last equation and expand the powers of $n+1$ you get $n^2+2n+1=3an^2+3an+a+2bn+b+c$ We need this to be true for all $n$, so $1=3a, 2=3a+2b, 1=a+b+c$ by equating the coefficients of each power of $n$. Solving gives $a=1/3, b=1/2, c=1/6$ Then if you check you can find $d=0$ – Ross Millikan Apr 13 '12 at 16:27

formula to calculate the square in $m \cdot n$ order: $[n(n+1)x(3m-n+1)]/6$

-
What does "mxn order" mean? A board of size $m\times n$ perhaps? A brief sentence fragment of this kind is almost never a good answer. – hardmath Jan 12 '14 at 18:04