A standard chess (or checker) board is an 8 x 8 grid, so how many squares are there in total? It's tempting to shout out "Sixty-four!" but I'm talking about squares of

all sizes, from 1 x 1, and 2 x 2, all the way up to 8 x 8. Go ahead and see if you can count them.

I tried counting up all the 1 x 1 squares, then all the 2 x 2s and 3 x 3s, but this takes awhile, and eventually I lost count. This method also doesn't lend itself very favorably to a general solution to the question "How many squares in an N x N board?" What if N = 100? How about if N = 1000? We need a more systematic and general approach.

My usual opening strategy when I come across a problem like this is to "brute force" a few small instances of the problem and check to see if a pattern emerges. From the pattern I try to see if I can come up with a formula, either by deriving it myself or, more typically, by searching for one online. Let's see if that works here.

For a 0 x 0 board there is a total of

0 squares.

For a 1 x 1 board there is a total of

1 square.

For a 2 x 2 board there is a total of

5 squares.

For a 3 x 3 board there is a total of

14 squares. One large 3 x 3 square, four distinct 2 x 2 squares (pictured below), and nine small squares.

For a 4 x 4 board there is a total of

30 squares, one large 4 x 4 square, four distinct 3 x 3 squares, nine distinct 2 x 2 squares, and sixteen small squares.

I think that's probably enough, because at this point I'm already starting to see a pattern develop. The sequence

0, 1, 5, 14, 30... probably doesn't mean much to most people, and I'll admit it didn't mean much to me either, at first. But when I looked just a little bit deeper, I noticed something familiar. Look at the

differences between each of the terms of the sequence.

1 - 0 = 1

5 - 1 = 4

14 - 5 = 9

30 - 14 = 16

...

All of the differences are perfect squares, so it looks like all you have to do to find the nth total in the sequence, is add n

^{2} to the previous total. This gives us the following

recurrence relation:

f(n) = f(n - 1) + n^{2}

We can use this relation to find out how many squares there are on an 8 x 8 chess board. Continuing on from where we left off:

f(5) = f(4) + 5^{2}

f(5) = 30 + 25 = 55

f(6) = f(5) + 6^{2}

f(6) = 55 + 36 = 91

f(7) = f(6) + 7^{2}

f(7) = 91 + 49 = 140

f(8) = f(7) + 8^{2}

f(8) = 140 + 64 = 204

But how do we confirm that? More importantly, what can you do if you didn't notice a pattern in the sequence in the first place? Searching Google for the sequence

0, 1, 5, 14, 30 gives surprisingly good results in this case, but it normally won't so I want to show you a better place to search. That better place is called the

Online Encyclopedia of Integer Sequences. (If you've been spending time at any of the

programming puzzle sites that I featured in my last post, you'll want to bookmark OEIS. It's a treasure trove of nerdy goodness.)

Searching OEIS for 0, 1, 5, 14, 30 turns up sequence

A000330. That sequence starts out

0, 1, 5, 14, 30, 55, 91, 140, 204...

which definitely seems to confirm the answer we got above.

Scanning through the comments I noticed this one:

Gives number of squares formed from an n X n square...

which is exactly what we're looking for. Further down the page you'll find plenty of formulae, and even source code in several different programming languages, for calculating the terms of the sequence. For example, here's a

closed form expression for calculating the nth term of the sequence:

f(n) = n * (n + 1) * (2 * n + 1) / 6

Solving for n = 8, we get

f(8) = 8 * (8 + 1) * (2 * 8 + 1) / 6

f(8) = 8 * 9 * 17 / 6

f(8) = 1224 / 6 = 204

which further confirms the answer we already knew.

If it seems like there are an awful lot of comments, formulae, and references on OEIS, that's because this particular sequence, the sum of the squares from 1 to n, turns up often in many areas of mathematics. Most of the sequences on OEIS won't have this much information to sift through, but you'll very often find something useful.

A ChallengeNow that you know a general strategy for solving puzzles involving integer sequences, why don't you give the following puzzle a try?

How many triangles (of all sizes) do you see in the equilateral triangle below?

Before counting triangles or searching online for the answer, see if you can build a sequence and find a pattern and a formula the way I did with the chess board problem above. Good luck!