How many squares?

Question

In a square grid made up of n^2 smaller squares, how many squares are there of any size? This I know:

Sigma(i=1,n) n^2

But what if we connect the opposite corners of every smallest square (so that now each smallest square is made up of 4 right-angle triangles)? Can anyone now find a common formula for total number of squares of any size? (The added diagonals create new squares that lie at 45 degrees in relation to the "obvious" squares)

Answer 1

First, recall that
∑(i=1,n) 1 = n
∑(i=1,n) i = n(n+1)/2
∑(i=1,n) 2i-1 = n²
∑(i=1,n) i² = n(n+1)(2n+1)/6
∑(i=1,n) i³ = n²(n+1)²/4
so that the base number of squares is: n(n+1)(2n+1)/6

Now let's consider the count of "diagonal squares" of size i when n is even (we'll add in your original squares at the end):
n: 1²
n-1: 2²
n-2: 3² + 4(1)
n-3: 4² + 4(1+1)
n-4: 5² + 4(1+ 3)
n-5: 6² + 4(1+1 + 3+1)
n-6: 7² + 4(1+ 3 +5)
n-7: 8² + 4(1+1 + 3+1 + 5+1)

Now we must very carefully sum these. First we have 1² + 2² + ... + n² = n(n+1)(2n+1)/6
Next, consider that for each odd numbered row, there are (n-k)/2 extra 1s floating around. Sum these to: 4(1+2+3+...+(n/2-1)) = 4(n/2-1)(n/2)/2

The remaining pairs of rows are doubled so that we sum: 8(1 + (1+3) + (1+3+5) + ... + (n/2-1)²) = 8(n/2-1)(n/2)(n-1)/6

Adding all of these up, the total number of diagonal squares is: n(2n+1)(2n-1)/6 so the total number of squares is:
n²(2n+1)/2


We're not done yet, since we have to consider odd sized squares (where n is odd). In this case, when we count the number of diagonal squares we get:
n: 0²
n-1: 1² + 4(1)
n-2: 2² + 4(1+1)
n-3: 3² + 4(1+ 3)
n-4: 4² + 4(1+1 + 3+1)
n-5: 5² + 4(1+ 3 +5)
n-6: 6² + 4(1+1 + 3+1 + 5+1)

Looking at the same three partial sums we get:
(n-1)n(2n-1)/6
4((n-1)/2)((n+1)/2)/2 and
8((n-1)/2)((n+1)/2)n/6

which sum to:
(n-1)(4n² + 4n + 3)/6

Adding this to the base number of squares yields the total number of squares as:
(2n³ + n² - 1)/2

If we compare this with what we got when n was even, we see that they are almost the same (a 1/2 is subtracted off for odd n). We can combine these as:

Total number of squares: floor(n²(2n+1)/2)

Answer 2

Answer (don't ask how I got there):

(Sigma(i=1,n) 3n^2 - n(mod 2)) - n^2

Answer 3

n*(n+1)(2n+1)/6