Overview
This is the fourth in a series of posts about a recreational maths problem - counting the number of squares (of all sizes) on a chessboard. The first three posts have shown that the number of squares of various sizes in an nxn grid is $\sum_{{i}={1}}^{n}i^2 = \frac{n(n + 1)(2n + 1)}{6}$. In this post we will solve the problem in a different way that will explain the structure of that formula.
All posts in this series
- Counting squares in a grid
- Guessing a closed form solution for the sum of squares
- A combinatorial solution for counting squares in a grid
A recap
In the first post of the series I showed that the number of squares in an n by n grid is $\sum_{{i}={1}}^{n}i^2$.
In the second post I used algebra to show that this summation equals $\frac{n(n + 1)(2n + 1)}{6}$.
But can we find a more direct link between this formula and the number of squares in an n x n grid? Preferably one that explains each part of the formula.
In this post I'm going to use an animated graphical demo to show you how to get to the formula directly. This will help us to build an intuition about the problem. In later blog posts we'll use that intuition to derive a very elegant solution.
tl;dr
If you don't feel like reading the full explanation, you can jump straight to the animations:
Skip straight to the first demo!Skip to the second demo
The solution approach
The formula can be rewritten as follows: $$ \begin{align*} f(n) & = \frac{n(n + 1)(2n + 1)}{6} \\ & = \frac{n(n + 1)}{2} \frac{2n + 1}{3} \\ & = \binom{n + 1}{2} . \frac{1}{3} . (2n + 1)\\ \end{align*} $$
I'll explain the three parts of this formula separately:
- There are $\binom{n + 1}{2}$ ways of selecting a vertical "slice" or subset of an n by n grid.
- The $\frac{1}{3}$ is because we're going to do this in three different ways.
- And we'll do this in a clever way, so that the number of squares that exactly fit the width of the 3 slices will always add up to $2n + 1$
Below is an animated demonstration for $n = 8$. You can see the 3 grids and an initial set of vertical slices of each grid.
When you click the start button, the demonstration will run through all the possible ways of generating vertical slices of the 3 grids. A pink square will slide down each vertical slice. The top left corner of the square is highlighted in a darker colour. As the pink square slides down the yellow slice, the dark pink corner will leave behind a "residue" of golden squares. This will make it easier to count the total number of squares that fit the width of the 3 grids.
Below the grids is a table which will be used to keep track of the total count. As the animation is running, watch how the rightmost column of the table always adds up to 17 (i.e. $2n+1$).
An interactive demonstration
Speed: Slow Medium Fast Very fast Align window to here Next demo
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|||||||||||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|||||||||||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|||||||||||||||||
| Combinations (5 at a time) | Pink squares per slice | Total squares | |||||
|---|---|---|---|---|---|---|---|
| # | i | j | A | B | C | A + B + C | |
| Total (all combinations): | |||||||
| $\binom{n + 1}{2} = \frac{n(n+1)}{2} = \frac{8 (8 + 1)}{2} = 36$ | $f(n) + f(n) + f(n) = 3 f(n)$ | $ = \binom{n + 1}{2} (2n + 1)$ | |||||
Note: Once the table has been fully populated, you will be able to:
- use the slider to scroll through the rows
- select an individual row by clicking on it
Explanation
I'll explain the solution in detail further down. But the essence of it is to:
- Choose a pair of numbers from the set {0, 1, ..., n}.
- Find three different ways of defining a vertical "slice" of the grid using that pair of numbers.
- Count the number of squares that fit the width $w$ of each slice exactly i.e. count how many $w$ x $w$ squares fit into the slice.
- The number of squares in each of the slices depends on the width $w$ of that slice, which depends on the specific pair of numbers chosen.
- But add the number of $w$ x $w$ squares in all three slices, and the answer is always $2n+1$, regardless of the numbers chosen.
I've created an interactive demonstration below which allows you to choose a pair of numbers and see the slices generated. Play around with it. You may be able to understand the solution without needing the explanation that follows.
Choose a pair of distinct numbers between 0 and n
First we choose any two numbers from the set $\{0, 1, ..., n\}$.
Let $i$ be the smaller and $j$ the larger of the two, so that $0 \le i \lt j \le n$.
A data representation
For each of the 3 grids we will use $i$ and $j$ to generate a slice of the grid. We will label the left and right edges of each grid $p$ and $q$.
Another demonstration
The previous demo showed all possible pink squares that fit into each vertical slice. This demo shows the possible top left hand corners of the squares in a golden colour. The number of golden squares is the total number of squares that fit into the 3 slices for a particular combination of $(i, j)$.
| Choose: | $i$ | $j$ | Align window to here | Previous demo |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|||||||||||||||||
| A | Formula | Value |
|---|---|---|
| $p$ | $i$ | |
| $q$ | $j$ | |
| $w$ | $j - i$ | |
| $s$ | $n - j + i + 1$ |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|||||||||||||||||
| B | Formula | Value |
|---|---|---|
| $p$ | $n - j$ | |
| $q$ | $n - j + i + 1$ | |
| $w$ | $i + 1$ | |
| $s$ | $n - i$ |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|||||||||||||||||
| C | Formula | Value |
|---|---|---|
| $p$ | $j - i - 1$ | |
| $q$ | $n - i$ | |
| $w$ | $n - j + 1$ | |
| $s$ | $j$ |
Squares in all three slices
| Grid | Size of squares ($w$ x $w$) | Formula for $s$ | Value (# of squares) |
|---|---|---|---|
| A | $n - j + i + 1$ | ||
| B | $n - i$ | ||
| C | $j$ | ||
| Total: | $2n + 1$ | 17 |
A few notes
I suggest taking a few moments to satisfy yourself that $p$ and $q$ are always valid for the three grids i.e. that $ 0 \le p \lt q \le n $. This can be deduced from equation (1) i.e. $0 \le i \lt j \le n$.
To be completely rigorous, we should also verify that $p$ and $q$ can map to any pair of integers from the set {0, 1, ..., n}, otherwise there could be squares which aren't being counted. I'm not going to go to those lengths, because the purpose of this blog post is to give you an intuitive understanding of why the sum of squares formula has the form it does. [Hint: Show that the mappings from ($i$, $j$ ) -> ( $p$, $q$ ) are bijections (one-to-one).]
Also take a look at the table of calculations. Notice how the $i$ and $j$ variables cancel out when you add the three formulae. This causes the total number of squares in the 3 slices to always be the same, no matter which pair of $i$ and $j$ values we choose.
A detailed explanation
Recall the formula we derived previously: $$ \begin{align*} \frac{n(n + 1)(2n + 1)}{6} & = \frac{n(n + 1)}{2} \frac{2n + 1}{3} \\ & = \binom{n + 1}{2} \frac{1}{3} (2n + 1)\\ \end{align*} $$
This gives a few clues for solving the problem. I'm going to break the formula into separate parts. Later I'll show you how to solve each part. Here's a brief overview of how each part of the formula will be used:
| # | Expression | Notes |
|---|---|---|
| 1. | $ \binom{n + 1}{2} $ |
Select two numbers from the set {0, 1, ..., n}. Treat these as the left and right edge of a vertical slice of the grid. This combination gives all possible ways of slicing the grid. |
| 2. | $ \frac{1}{3} $ |
Find two other ways of using the same two numbers to define vertical slices of the grid. This gives three different ways of partitioning the grid into slices. Add up all the squares that fit exactly in the 3 slices defined by the pair of numbers. But that means that every square in the final total is going to be counted 3 times. So we need to divide the total by 3. |
| 3. | $ 2n + 1 $ |
Count the number of squares which fit into each slice exactly (i.e. with the same width as the slice). Each pair of numbers gives 3 different vertical slices. Each slice will accommodate a different number of squares. But together the 3 slices are always going to have exactly $2n + 1$ squares. |
Conclusion
This post gives us an intuitive idea of why the formula for the sum of squares looks like $\frac{n(n + 1)(2n + 1)}{6}$.
But can we do better than this?Where do the three mappings from $(i, j)$ to $(p, q)$ come from? Must we rely on trial and error to determine them. Or is there a more satisfying way of deriving them?
And where does the $2n + 1$ term come from? We used algebraic cancellation to determine it. But can we find a more intuitive explanation for why it must have that specific form?
In the next few blog posts, I am going to answer these questions. In the process we're going to derive a very elegant solution which addresses each of these questions.
