Bill the Lizard: How many squares are there on a chess board?

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

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 n2 to the previous total. This gives us the following recurrence relation:

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) = 30 + 25 = 55

f(6) = f(5) + 62

f(6) = 55 + 36 = 91

f(7) = f(6) + 72

f(7) = 91 + 49 = 140

f(8) = f(7) + 82

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

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:

Solving for n = 8, we get

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 Challenge

Now 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?