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.

Your attempts are admirable, however.  Please keep up that activity.

-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/