Miscellaneous 2-1: How many Shapes, Part 1: How many Squares?

Part 1 of 4 of How Many Shapes?

[Level 0]

I can't really classify this a Problem Post, because its roots lie more in Internet culture than in math contests.

Remember this nasty little thing making the rounds on social media?

Once you read this post, 100% will put this puzzle behind us.

We could just manually count squares, but that's boring, and we want to find a method to do this for huge squares.

PROBLEM 1
Devise a method to rapidly solve problems of this type, no matter the size of the square grid.

Okay, so the two little $2\times 2$ squares in the middle are in the way, so let's focus on the main $4\times 4$ grid first. Let's be systematic and count squares of size 1, 2, 3, and 4 separately:

© Project Phi 2014. All rights reserved.

So there's one size 4 square, four size 3 squares, nine size 2 squares, and sixteen size 1 squares. One, four, nine, sixteen -- aren't these perfect square numbers?

It's not a coincidence that they are perfect square numbers. How do we figure this out? Well, given a certain size of square to count, let's look at the number of places the upper left squarelet (the size 1 square in the upper leftmost part of the big square) can occupy.

Size 1
The upper left squarelet of a size 1 square is the whole square! So the squarelet can be placed in any of the $4\times 4 = 16$ places.

Size 2
The upper left squarelet of a size 2 square can only be in the first three rows and the first three columns of the grid. Why? If you forced it onto the fourth row, or the fourth column, the rest of the square won't fit! So we have $3\times 3 = 9$.

Size 3
Same as the size 2 square, the upper left squarelet can only be in the first two rows and the first two columns of the grid. So we have $2\times 2 = 4$.

Size 4
Now the square is so big, the upper left squarelet can only be in the first row and the first column of the grid. So we have $1\times 1 = 1$.

So now we have a formula for the number of squares of a particular size!

DISCOVERY/SOLUTION 1
In an $n\times n$ square grid, there are $(n-k+1)^2$ squares of size $k$, for $k=1,2,\ldots,n$.
This means there are $1^2 + 2^2 + \cdots + n^2$ squares of all sizes.

To demonstrate, we plug in to the original question:

ANSWER TO THE ORIGINAL QUESTION
In total, the $4\times 4$ grid has $1+4+9+16=30$ squares. Each of the little $2\times 2$ grid has $5$ squares each, so we have $30+5+5=\boxed{40}$ squares all in all.

And, to make things better, we have a formula for the sum of squares:

ANSWER TO THE ORIGINAL QUESTION, IMPROVED\[\frac{4\times5\times9}{6}+2\times\frac{2\times3\times5}{6}=\boxed{40}\] 

We have a nice formula. But we can do better, right?

CAN WE DO BETTER?

• What if the original grid were a rectangle, instead of a square? Or an irregular figure?
• What if we were counting rectangles instead of squares?
• What if some of the grid 'wires' are missing?
• What if we're working on a triangular grid, counting triangles? Does our logic still apply?

We'll tackle these and more on a subsequent Problem Post.