Given an n*m grid with n > m.

Orient the grid so n is its width. Divide the grid into two portions, an m*m square on the left and an (n-m)*m rectangle on the right. Count the squares that have their upper right-hand corners in the m*m square. There are m^2 of size 1*1, (m-1)^2 of size 2*2, ... up to 1^2 of size m*m. Now look at the n-m columns of lattice points in the rectangle on the right, in which we find upper right-hand corners of squares not yet counted. For each column we count m new 1*1 squares, m-1 new 2*2 squares, ... up to 1 new m*m square.

Combining all these counts in summations

m m

total = sum i^2 + (n - m) sum i

i=1 i=1

(2m + 1)(m + 1)m (n - m)(m + 1)m

= ---------------- + ---------------

6 2

= (3n - m + 1)(m + 1)m/6

-- David Karr

#### PHP Warning

lib/DbaDatabase.php:154: Warning: dba_optimize() [<a href='function.dba-optimize'>function.dba-optimize</a>]: You cannot perform a modification to a database without proper access

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access