Treebeard's Homepage : Stumpers

Treebeard's Stumper Answer
15 May 98

Chess Squares (continued)
The Gory Details!

"With some algebra" was an understatement. Here are the details.

In general, the number of squares on a n-by-m chessboard, with n >= m, is given by the m terms of the series:

     sum = (m)(n) + (m-1)(n-1) + (m-2)(n-2) + ... + (1)(n-m+1)
Consider the individual terms, arranged to show the pattern:
     (m)  (n)   = mn
     (m-1)(n-1) = mn -  (n + m) + 1
     (m-2)(n-2) = mn - 2(n + m) + 4
     (m-3)(n-3) = mn - 3(n + m) + 9
                .
                .
                .
Adding the first m terms of this series vertically gives:
     sum = m(mn) - [1+2+3+...+(m-1)](n+m) + [1+4+9+...+(m-1)(m-1)]
The sum of the first m integers is m(m+1)/2, and the sum of the first m squares is m(m+1)(2m+1)/6, but we only need the first m-1 sums. So this becomes:
                   (m-1)(m)         (m-1)(m)(2m-1)
     sum = m(mn) - -------- (n+m) + --------------
                       2                   6
Now it's just a matter of expanding and collecting terms with basic algebra. Note that I'm writing m2n as mmn to simplify the HTML code for this page.
                 3(m-1)(m)(n+m) - (m-1)(m)(2m-1)
     sum = mmn - -------------------------------
                               6


                 (m)(m-1) [3(n+m)-(2m-1)]
         = mmn - ------------------------
                           6


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


           6mmn - mmm - 3mmn + 3mn + m
         = ---------------------------
                     6


           3mmn - mmm + 3mn + m
         = ---------------------
                     6


           m (3mn - mm + 3n + 1)
         = ---------------------
                     6


           m (m+1) (3n-m+1)
         = ----------------
                  6
And there's the final form:
     sum = m(m+1)(3n-m+1)/6
Heck of a way to spend a Saturday morning, but I'm not complaining. This was fun!

Back to Stumper Answer


Last modified .

Copyright © 1998 by Marc Kummel / mkummel@rain.org