Treebeard's Homepage : Stumpers

# Treebeard's Stumper Answer15 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!