Ya clarificó el compañero Chris de qué manera entendió él el problema, y ya presentó una respuesta parcial. La manera como yo entendí la pregunta, era que había que contar el número de cuadrados que son una unión de cuadrados unitarios (es decir, "cuadrado de tamaño $n$" significa cuadrado de lados paralelos a los ejes cartesianos, con vértices en los puntos de la retícula y cuyo lado tiene longitud $n$).
Así, supongamos que tenemos una cuadrícula de dimensiones $n\times m$ y supongamos, por simplicidad, que $n\leq m$. Contemos los cuadrados de tamaño $k$ dentro de esta cuadrícula (obviamente, para que esto tenga sentido, necesitamos que $1\leq k\leq n$). Digamos que indexamos los cuadrados de nuestra cuadrícula, contando de izquierda a derecha y de abajo hacia arriba (entonces, el cuadrado del extremo inferior izquierdo es el que tiene índice $(1,1)$, el del extremo inferior derecho tiene índice $(n,1)$, el de la esquina superior izquierda tiene índice $(1,m)$ y el cuadrado de la esquina superior derecha está indexado por $(n,m)$). Nótese que cada cuadrado de tamaño $k$ tiene una esquina inferior izquierda, cuyo índice $(i,j)$ debe de satisfacer que $i+k-1\leq n$ y $j+k-1\leq m$ (pues de lo contrario el cuadrado "se saldría" de nuestra cuadrícula). Por lo tanto, el índice $(i,j)$ de la esquina inferior izquierda de cualquier cuadrado de tamaño $k$ debe satisfacer que $i\leq n+1-k$ y $j\leq m+1-k$. Recíprocamente, para cada cuadrado cuyo índice $(i,j)$ satisface las desigualdades previas, es posible utilizarlo como esquina inferior izquierda de un cuadrado de tamaño $k$ (pues las desigualdades aseguran que dicho cuadrado "sí cabe" dentro de nuestra cuadrícula). Finalmente, es claro que distintos cuadrados de tamaño $k$ tienen distinta esquina inferior izquierda. Lo que esto muestra es que los cuadrados de tamaño $k$ están en biyección con los pares $(i,j)$ con $1\leq i\leq n+1-k$ y $1\leq j\leq m+1-k$, por lo tanto hay $(n+1-k)(m+1-k)$ de ellos. Esto significa que el número total de cuadrados en la retícula de tamaño $n\times m$ es:
$\sum\limits_{k=1}^{\min\{n,m\}}(n+1-k)(m+1-k)$.
Cualquier sugerencia para simplificar esta expresión será bienvenida. En el caso particular cuando $n=m$ obtenemos $\sum_{k=1}^n(n+1-k)^2=\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$.
