Given a grid that is NxN, how many squares can you make by connecting the dots?
The answer I got is this:
The reason is pretty neat. For an example, let's use a 5x5 grid.
Here is the sum:
1 * (5 − 1)2 + 2 * (5 − 2)2 + 3 * (5 − 3)2 + 4 * (5 − 4)2
1 * 16 + 2 * 9 + 3 * 4 + 4 * 1
Let's start with the first term: 1 * 16. When you have a 2x2 matrix, you can make 1 square. And in a 5x5 matrix, you can make 16 of those squares.
Next is 2 * 9. In a 3x3 matrix you can make 2 squares (as below) and there are 9 places you can do this in a 5x5 matrix.
This continues for 3 * 4 as there are 4 places you can make the 3 squares below.
And finally, you can make 4 squares out of the largest block just one time in a 5x5 square.
I thought this was really interesting and elegant. So the next thing I did was figure out the answer for any matrix of NxM. It is actually pretty simple. The answer for the NxN matrix was the sum of x(N-x)^2 because N-x was the area.. so with an NxM matrix the sum is like this: