Finding a proof to the 'squares' problem

Question

I am trying to find a proof for the general case of the solution to the 'Squares' Problem.

This is what I have managed to figure out: If n is the number of squares in the top row, then the number of 3-by-3 squares is given by the formula $(n-2)^2$ I know this works for $n=4$ (the case in the diagram), because there are four 3-by-3 squares. It also works for $n=5$ and $n=6$, because I have drawn the cases and counted the 3-by-3 squares.

I know empirical evidence such as this does not constitute proof, so my answer to the $n=60$ case, that there are $58^2$ 3-by-3 squares remains unproven.

I have used the induction tag only because I tried (and failed) to use this method this afternoon, I will be happy with any kind of proof.

Answer 1

To make a $3 \times 3$ square you must chose three consecutive rows and three consecutive columns. How many ways are there to make such a choice? Well there are $n-2$ ways to choose the rows and $n-2$ ways to choose the columns in an $n \times n$ square. Thus your $(n-2)^2$ is the correct count, and this is the reason why.

Answer 2

You can note that the central square of the $3\times3$ square set can correspond to any square of the $n\times n$ square set, with the exception of those on the borders. This directly leads to the solution $(n-2)^2$ that you found.