The chessboard is an inessential detail, so let's re-phrase the question:

How many squares, of any size, are there on an 8x8 grid?

Eventually, it'll be:

How many squares, of any size, are there on an n x n grid?

Some tools that I'll be using to solve this problem:

- Sequences
- Basic arithmetic
- A nifty property of sequences called Δ-k constants and which help us find "closed" formulas (more on that later)

As is common in problem solving, the simplest examples illustrate the problem and give a starting point.

#### A 0x0 grid

There are zero squares of any size.

#### A 1x1 grid

There is one square of size 1x1.

#### A 2x2 grid

This is where the "of any size" bit takes on meaning. In a 2x2 grid there are actually 5 squares "of any size." This is because a 2x2 grid contains 4 1x1 squares and then a single square of size 2x2.

You can see here that there are 5 squares of multiple sizes. There are four 1x1 squares and then a 2x2 square (the dashed-square). There are 4 + 1 = 5 total squares.

#### A 3x3 grid

A 3x3 grid is nothing but nine 1x1 squares, four 2x2 squares, and one 3x3 square. I've highlighted one of the four 2x2 squares (they contain numbers `1,2,4,5`

). There are 9 + 4 + 1 = 14 total squares.

#### A pattern emerges

Enter sequences:

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order does matter

Let's write the total number of squares as a sequence. The "index" of each item in the sequence represents `n`

in the `n x n`

grid:

`0, 1, 5, 14`

Each element in our total number of squares sequence can be defined as a *the sum of all previous totals up to, and including, the current total.* Put another way:

0x0 -> 0 squares (0)

1x1 -> one 1x1 square + zero 0x0 squares (1 + 0)

2x2 -> four 1x1 squares + one 2x2 square + zero 0x0 squares (4 + 1 + 0)

3x3 -> nine 1x1 squares + four 2x2 squares + one 3x3 square + zero 0x0 squares (9 + 4 + 1 + 0)

If n = 3, the number of squares on your n x n grid is: 0^{1} + 1^{2} + 2^{2} + 3^{2} or `0 + 1 + 4 + 9 = 14`

.

Answering our original question is now easy.

How many squares of any size are there on an 8x8 grid?

You just sum the squares from 0 to n.

`sum([i**2 for i in range(0, 9)]) # 204`

Recall that `range`

counts from `0`

up to `9`

, but not including `9`

.

#### Finding a closed formula

We can find a closed formula to calculate this without the summation. For example, you could add all the terms of a sequence of 1, 2 ,3, ..., n to find the total. Or your could use this handy equation:

`total = (n(n+1)) / 2`

Compare: `1+2+3+4+5 = 15`

and `(5(5+1))/2 = 15`

.

Let's take our sequence and extend it with a few more elements:

`1, 5, 14, 30, 55`

We can find a pattern of sorts by taking the differences between terms. We can form another sequence of terms (the differences) which will always be one element shorter than the original.

```
1, 5, 14, 30, 5
4, 9, 16, 25
5, 7, 9
2, 2
```

We took differences three times in order to reach a constant. What we just did there was find the Δ-k constant. In this case, Δ^{3} constant.

This is important for this reason:

The closed formula formula for a sequence will be a degree k polynomial if and only if the sequence is Δ

^{k}-constant

This means our closed formula will be a degree k (3) polynomial or:

a_{n} = an^{3} + b^{2} + cn + d

Note: a_{n} represents the nth element of a, which is our sequence: `0, 1, 5, 14, 30, 55`

. The 0th term is 0, the 1st term is 1, the second term is 5, etc.

a_{0} = 0 = a(0)^{3} + b(0)^{2} + c(0) + d

The above simplified to: d = 0—an important piece of information.

a_{1} = 1 = a(1)^{3} + b(1)^{2} + c(1) + 0

a_{1} = 1 = a + b + c

a_{2} = 5 = a(2)^{3} + b(2)^{2} + c(2) + 0

a_{2} = 5 = 8a + 4b + 2c

a_{3} = 14 = a(3)^{3} + b(3)^{2} + c(3) + 0

a_{3} = 14 = 27a + 9b + 3c

Now we have a system of equations which we can solve for to get the values of a, b, and c.

a_{1} = 1 = a + b + c

a_{2} = 5 = 8a + 4b + 2c

a_{3} = 14 = 27a + 9b + 3c

To save time, I will wave my hand and solve that system:

a = 1/3

b = 1/2

c = 1/6

With these values, we now have our closed formula:

a_{n} = 1/3(n)^{3} + 1/2(n)^{2} + 1/6(n)

If n = 8: `1/3(8)^3 + 1/2(8)^2 + 1/6(8) = 204`

If n = 800: `1/3(800)^3 + 1/2(800)^2 + 1/6(800) = 170986800`

## Discussion