Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/