How many squares (including tilted ones) can be built with vertices on a grid of $n\times n$ points? The following may be useful: $\sum\limits_{k=1}^n k^2=\frac{n(n+1)(2n+1)}{6}$ and $\sum\limits_{k=1}^n k^3=\frac{n^2(n+1)^2}{4}.$
1. Four points on a Cartesian grid form a square of area $100$ (in grid area units) with sides parallel to the grid. How many points lie on the boundary of this square?
2. Could you have a tilted square of area $100$ (in grid area units) with vertices on the grid?
3. Simplify $\sum_{k=0}^{n}k(n-k).$
4. Three points with coordinates $(1,3),$ $(2,1)$ and $(4,2)$ lie on the perimeter of a square. What is the smallest such square (in terms of area)?

How many squares with sides parallel to the grid can be built?

For a given $k \le n,$ how many sub-grids of $k\times k$ points are there?

For a given sub-grid of $k\times k$ points, how many squares with vertices on the outer points of the sub-grid can be built?

How can we incorporate that for all values of $k?$

… knowing that there are $(n-k+1)^2$ sub-grids of $k\times k$ points and $k-1$ squares (including tilted ones) per each such sub-grid?

We can first count the number of different sub-grids of size $k\times k,$ then count the number of squares with vertices only on the outer points of each sub-grid. This avoids counting duplicates (can you see why?).

The number of sub-grids of size $k\times k$ is $(n-k+1)^2$ because $n-k+1$ is the number of possible horizontal (or vertical) shifts of such a sub-grid.

For each $k\times k$ sub-grid, a square with vertices on the outer points of the sub-grid is uniquely defined by the position of the vertex on one side of the sub-grid. Hence, there are $k-1$ different such squares.

Finally, the total number of squares is the sum over the sub-grids: \begin{aligned} N&=\sum_{k=2}^{n} (k-1)(n-k+1)^2 \\ &=\sum_{j=1}^{n-1} (n-j)j^2 \\ &= n \sum_{j=1}^{n-1}j^2 - \sum_{j=1}^{n-1}j^3 \\ &= \frac{n^2(n+1)(2n+1)}{6}-\frac{n^2(n+1)^2}{4} \\ &= \frac{n^4-n^2}{12}, \end{aligned} where we made the change of variable $j=n-k+1.$