Counting Geoboard Squares

[Includes tilted squares; see

http://nzmaths.co.nz/resource/lots-squares.]

How many squares are there in a rectangular Geoboard with M x N nails, where M and N are positive integers?

Without loss of generality assume N >= M and M is along the vertical side of the Geoboard. So the Geoboard may be wider than it is tall.

Let m = M - 1 and n = N - 1 so m and n are counting the intervals between the nails. m is the number of rows and n is the number of columns.

Number of 1x1 squares = mn with 1 square each (no tilted)

Number of 2x2 squares = (m-1)(n-1) with 2 squares each => 2(m-1)(n-1)

Number of 3x3 squares = (m-2)(n-2) with 3 squares each => 3(m-2)(n-2)

Number of 4x4 squares = (m-3)(n-3) with 4 squares each => 4(m-3)(n-3)

…

Number of k x k squares = (m-(k-1))(n-(k-1)) with k squares each => k(m-(k-1))(n-(k-1))

So we want the sum of all these:

S = sum{k=1,m}(k(m-(k-1))(n-(k-1)))

S = sum{k=1,m}(k(m-k+1)(n-k+1))

S = sum{k=1,m}(k(m(n-k+1)-k(n-k+1)+1(n-k+1)))

S = sum{k=1,m}(k(mn-mk+m-kn+k^2-k+n-k+1))

S = sum{k=1,m}(k(k^2-mk-nk-2k+mn+m+n+1))

S = sum{k=1,m}(k(k^2-(m+n+2)k+(mn+m+n+1)))

S = sum{k=1,m}(k^3-(m+n+2)k^2+(mn+m+n+1)k)

S = sum{k=1,m}(k^3)-(m+n+2)sum{k=1,m}(k^2)+(mn+m+n+1)sum{k=1,m}(k)

S = (m^2)((m+1)^2)/4 - (m+n+2)(m)(m+1)(2m+1)/6 + (mn+m+n+1)(m)(m+1)/2

Formulas used are on

http://en.wikipedia.org/wiki/Summation.

12S = 3(m^2)((m+1)^2) - 2(m+n+2)(m)(m+1)(2m+1) + 6(mn+m+n+1)(m)(m+1)

12S = m(m+1) (3m(m+1) - 2(m+n+2)(2m+1) + 6(mn+m+n+1))

12S = m(m+1) (3m^2 + 3m - (m+n+2)(4m+2) + 6mn + 6m + 6n + 6)

12S = m(m+1) (3m^2 + 3m - m(4m+2) - n(4m+2) - 2(4m+2) + 6mn + 6m + 6n + 6)

12S = m(m+1) (3m^2 + 3m - 4m^2 - 2m - 4mn - 2n - 8m - 4 + 6mn + 6m + 6n + 6)

12S = m(m+1) (3m^2 - 4m^2 + 3m - 2m - 8m + 6m - 4mn + 6mn - 2n + 6n - 4 + 6)

12S = m(m+1) (-m^2 - m + 2mn + 4n + 2)

12S = m(m+1) (-(m^2 + m - 2) + 2n(m + 2))

12S = m(m+1) (-(m + 2)(m - 1) + 2n(m + 2))

12S = m(m+1) (m + 2)(-(m - 1) + 2n)

S = m(m + 1)(m + 2)(2n - m + 1)/12, m and n are side intervals, m <= n

Converting back to using number of nails instead of intervals:

m = (M - 1) and n = (N - 1)

S = m(m + 1)(m + 2)(2n - m + 1)/12

S = (M - 1)((M - 1) + 1)((M - 1) + 2)(2(N - 1) - (M - 1) + 1)/12

S = M(M - 1)(M + 1)(2N - M)/12, M and N are nails on sides, M <= N