How many squares on a grid

Say the total number of squares we can draw on an $n \times n$ grid is $f(n)$ .

Start drawing a square from a point on the grid $A(p,q)$ . Draw the next vertex at $B(p+u,q+v)$ . This defines the remaining vertices; the full set is $\begin{aligned} &A(p,q) \\&B(p+u,q+v)\\&C(p+u-v,q+v-u)\\&D(p-v,q-u) \end{aligned}$

To make sure it fits on the grid, we need $\begin{aligned} 0\le p-v, &\;\;\; p+u \le n \\ 0\le q-u, &\;\;\; q+v \le n \end{aligned}$

This gives $n+1-u-v$ possible values of $p$ and the same for $q$ . For a fixed pair $(u,v)$ satisfying $u+v 0\le n$ , this means there are a total of $(n+1-u-v)^2$ possible starting points $(p,q)$ so that all vertices are on the grid.

In order to avoid double-counting we just need to insist that $u \ge 0$ and $v \ge 1$ (this avoids counting squares with sides on the gridlines twice).

This gives the formula $f(n)=\sum_{u=0}^{n-1}\sum_{v=1}^{n-u} (n+1-u-v)^2$

...which looks pretty horrendous, but after doing the paperwork** we get the surprisingly neat $f(n)=\frac{1}{12}n(n+1)^2 (n+2)$

In particular, $f(16)=\boxed{6936}$ .

---

**There are various ways to work out the sum, such as:

• Expand, and use the formulas for $\sum k$ and $\sum k^2$ repeatedly

• Use Wolfram|Alpha to help

• Recognise it will be a polynomial in $n$ , calculate some values and use a difference table to work out coefficients

I suspect there's a clever way to use symmetry here too, but perhaps that's a bonus question?