Associated Topics || Dr. Math Home || Search Dr. Math

### Checkerboard Problem

```
Date: 07/30/97 at 00:18:38
From: Anonymous
Subject: Checkerboard Problem

Dear Dr. Math,

I'm a student in New Iberia, Louisiana and I love math. I work on
problems for fun. Here's one I've been wondering about.

I saw the problem you answered about how many squares are on the
checkerboard. It made me think of whether or not there's a pattern
developing that would allow the formula to go in all powers.

For example, to add up all the numbers from one to n you would use
n(n+1)/2. To add up all the squares from the square of 1 to n^2 you
would use n(n+1)(2n+1)/6, a product of the previous equation when you
multiply it by 2n+1/3.

Then I thought I'd try to get a new formula by multiplying that by
3n+1/4, and it kept coming out one less than the answer. I did some
more figuring and I think for cubes it would be

[n(n+1)(2n+1)(3n+1)+24]/24

It seems to work when I try it, but could the pattern go on even
further?
```

```
Date: 08/01/97 at 10:16:52
From: Doctor Rob
Subject: Re: Checkerboard Problem

You are looking at a very interesting problem, and one which will lead
you eventually into some advanced mathematics.  The subject is called
the Calculus of Finite Differences.

Let S(k,n) denote the sum of the first n k-th powers:
S(k,n) = 1^k + 2^k + ... + n^k.

It is clear that
S(0,n) = n.

You point out above that
S(1,n) = n*(n + 1)/2,
and
S(2,n) = n*(n + 1)*(2*n + 1)/6.

The simplest formula for k = 3 is
S(3,n) = [n*(n + 1)/2]^2.

This disagrees with your conjecture above.  I looked up formulae for
larger values of k, and found the following:

S(4,n) = n*(n + 1)*(2*n + 1)*(3*n^2 + 3*n - 1)/30
S(5,n) = n^6/6 + n^5/2 + 5*n^4/12 - n^2/12
S(6,n) = n^7/7 + n^6/2 + n^5/2 - n^3/6 + n/42
S(7,n) = n^8/8 + n^7/2 + 7*n^6/12 - 7*n^4/24 + n^2/12

The pattern here is not obvious, but parts of it are.
One general formula is given by

S(k,n) = n^(k+1)/(k+1) + n^k/2 + (1/2)*C(k,1)*B(1)*n^(k-1)
- (1/4)*C(k,3)*B(2)*n^(k-3) + (1/6)*C(k,5)*B(3)*n^(k-5)
- ...

Here the last term involved n^2 if k is odd and n^1 if k is even.
C(k,i) is the binomial coefficient k!/(i!*[k-i]!). B(i) is a so-called
Bernoulli number. The first few are B(1) = 1/6, B(2) = 1/30,
B(3) = 1/42, B(4) = 1/30, B(5) = 5/66, B(6) = 691/2730, B(7) = 7/6.

There are complicated formulae for the Bernoulli numbers, one of which
is the following:

B(i) = 2*[(2*i)!]*(2*Pi)^(-2*i)*[1^(-2*i) + 2^(-2*i) + 3^(-2*i) + ...]

(It may appear that this might not be a simple number like 1/30, but
such is always the case).

The defining properties of S(k,n), k >= 0 are:

S(k,n) - S(k,n-1) = n^k, for every n > 0,   and   S(k,0) = 0.

The expression on the left is called the first difference of the
function S(k,n) with respect to n. The whole equation is one of a
class called difference equations. The hard part it to solve this
equation. That is where the Bernoulli numbers and binomial
coefficients come in.

So you were right that there is a pattern, but wrong in your guess as
to what that pattern might be.  It is far more complicated than you
thought.

-Doctor Rob,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/

```

```
Date: 08/03/97 at 13:36:41
From: Anonymous
Subject: Re: Checkerboard Problem

Thank you. This explains why the formula I found only works for the
number 3.

I am a ninth grader in New Iberia, Louisiana and I have a great
interest in mathematics.
```

```
Date: 08/07/97 at 13:48:21
From: Doctor Rob
Subject: Re: Checkerboard Problem

Keep up your interest in mathematics!

-Doctor Rob,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search