How Many Squares?
Let’s gather some data. How many squares on a 1-by-1 grid? Easy! One.
How about a 2-by-2 grid?
There’s four 1-by-1 squares and one 2-by-2 square, for a total of 4+1=5 squares.
How about a 3-by-3 grid?
1-by-1 squares: 9
2-by-2 squares: 4
3-by-3 squares: 1
Total squares: 9+4+1=14
How about a 4-by-4 grid?
Following the patterns unfolding above, here’s my guess: 16+9+4+1=30 squares.
Extending that pattern further, we’d get:
Grid width | Grid height | 1-by-1s | 2-by-2s | 3-by-3 | 4-by-4 | 5-by-5 | … | Total |
1 | 1 | 1 | 0 | 0 | 0 | 0 | | 1 |
2 | 2 | 4 | 1 | 0 | 0 | 0 | | 5 |
3 | 3 | 9 | 4 | 1 | 0 | 0 | | 14 |
4 | 4 | 16 | 9 | 4 | 1 | | | 30 |
5 | 5 | 25 | 16 | 9 | 4 | 1 | | 55 |
… | … | | | | | | | |
10 | 10 | | | | | | | 385 |
Where’s that total in the 10-by-10 grid come from? I noticed we’re dealing with a sum of squares.
So we get 100+81+...+4+1=385 total squares.
What about a generalization?
Let’s take a look at some differences.
Grid width | Grid height | Total | 1st diff. | 2nd diff. | 3rd diff. |
1 | 1 | 1 | | | |
2 | 2 | 5 | 4 | | |
3 | 3 | 14 | 9 | 5 | |
4 | 4 | 30 | 16 | 7 | 2 |
5 | 5 | 55 | 25 | 9 | 2 |
6 | 6 | 91 | 36 | 11 | 2 |
No surprise that the first differences are perfect squares. So we end up with constant third differences, and we’re looking at a cubic function.
I ran regression in Desmos, and then tinkered with a bit of factoring to get this:
f(n)=6n(n+1)(2n+1)
What about non-square grids? Let’s gather some more data.