Squares on a grid

We can do this by brute force. For a $n \times n$ grid, the number of grid squares is simply the sum of squares, as there is $1$ largest square, $4$ next largest square, etc, so we have

$\displaystyle\sum _{ k=1 }^{ n }{ { k }^{ 2 } } =\dfrac { 1 }{ 6 } n(n+1)(2n+1)=\{ 1,5,14,30,55,91,...)$

Figuring out the number of tilted squares is harder, but we can discern a pattern by inspection, looking at the number of different sized tilted squares (touching sides of largest square grids to the smallest) by way of a kind of an induction

$0=0\\ 1=1(1)\\ 6=1(2)+4(1)\\ 20=1(3)+4(2)+9(1)\\ 50=1(4)+4(3)+9(2)+16(1)\\ 105=1(5)+4(4)+9(3)+16(2)+25(1)$

So that we have

$\displaystyle\sum _{ k=1 }^{ n }{ { k }^{ 2 } } (n-k)=\dfrac { 1 }{ 12 } (n-1){ n }^{ 2 }(n+1)=\{ 0,1,6,20,50,105,...)$

From these two, we can show that

$\dfrac { 1 }{ 6 } n(n+1)(2n+1)+\dfrac { 1 }{ 12 } (n-1){ n }^{ 2 }(n+1)=\dfrac { 1 }{ 12 } n{ (n+1) }^{ 2 }(n+2)$

And thus the conjecture is proven. I’m sure there might be an more elegant way of showing this, which would mean a quicker way of working out the total number of squares, grid and tilted, in a square lattice, but I’d have to think about it.

How do we generalize this for a n*m grid?

I found a bijection, but I can't explain the rule. But basically, for all the squares on the $n\times n$ grid, you move one corner NE $\dfrac{1}{\sqrt{2}}$ units, one corner NW$\dfrac{1}{\sqrt{2}}$ units, one corner SW $\dfrac{1}{\sqrt{2}}$ units, and one corner SE $\dfrac{1}{\sqrt{2}}$ units.

Fine problem https://oeis.org/A002415

On the left side are a series of squares of increasing sides, with inscribed tilted squares. It is readily seen that the number of inscribed tilted squares in a $n-1\times n-1$ square plus $1$ equals to the number of inscribed tilted squares in a $n\times n$ square.

On the right side note that for any $n\times n$ square there is $1$ largest grid square, $4$ next largest grid square, $9$ next largest, etc. This corresponds to the number of grid squares in the $n-1\times n-1$ square, i.e. $1$ largest grid square, $4$ next largest square, etc. Hence, there's a bijection of the number of grid squares, but for the number of the smallest grid square in the $n\times n$ square. But since we are counting only tilted squares in the $n\times n$ square, the count of the smallest grid square does not matter.

Every grid square of any size has associated with it tilted squares that are inscribed in it, and every tilted square of any size has associated with it a grid square that circumscribes it. So, counting all the tilted squares in a $n\times n$ square is the same as counting all the squares, grid and titled, in a $n-1\times n-1$ square. This is the bijection.

Spoiler space. If you do not want to see the bijection, then don't read the sub-comments.