Generalized Gauss Sum

Date: 07/18/2003 at 14:18:45
From: Jamie Bruce
Subject: Generalized Gauss Sum

Is there a formula that computes the sum of numbers from m to n, where 
m and n could be positive, negative, or zero?

I know you can compute the sum of numbers from 1 to n quite easily ... 
n(n+1)/2, but was not sure if a formula existed for the 
general case.

Date: 07/18/2003 at 14:23:43
From: Doctor Roy
Subject: Re: Generalized Gauss Sum

Hi,

Thanks for writing to Dr. Math.

Let's start simply and work our way up.

Let's say we want to find the sum of the numbers from m to n, where
m<n and m and n are both positive.

We know the sum of the numbers from 1 to n:

    n(n+1)/2

We also know the sum of the numbers from 1 to m-1:

    m(m-1)/2

The sum of the numbers from m to n (including m) should then be:

    n(n+1)/2 - m(m-1)/2

We subtract the sum of the numbers from 1 to m-1, leaving the sum of
the numbers from m to n.

Now, let's add a complication. Let's say that m is negative and n is
positive. Since zero is zero, it does not contribute to the sum. Then, 
the sum is also easy to find. Let's say that |m| is the absolute value 
of m:

Sum from 1 to n + sum from m to -1 = sum from m to n, or:

      n(n+1)/2 - |m|(|m|+1)/2

 - |m|(|m|+1)/2  is the sum of the numbers from m to -1.  We simply
add them to the sum of the numbers from 1 to n.  

If both are negative, you can use tricks similar to the one above to
calculate the sum.  

Does this help?  Please feel free to write back with any questions you
may have.

- Doctor Roy, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 07/18/2003 at 14:40:31
From: Doctor George
Subject: Re: Generalized Gauss Sum

Hi Jamie,

Thanks for writing to Doctor Math.

You can derive the formula like this. Assume that m < n, and define 
k = n - m. Now the sequence looks like this.

    m      m+1     m+2    ...   m+k-2    m+k-1    m+k

Now reverse the sequence like this.

    m+k    m+k-1   m+k-2  ...   m+2      m+1      m

Now add the terms from the forward and reverse sequences.

    2m+k   2m+k    2m+k   ...   2m+k     2m+k     2m+k

Now we have

           Sum = (2m + k)*(k + 1)

               = [2m + (n-m)] * (n - m + 1)

               = (m + n) * (n - m + 1)

But we have accounted for each term twice, so we divide by 2 to get

           Sum = (m + n) * (n - m + 1) / 2

You can see that if m = 1 we get the familiar result for a sequence 
that begins with 1.

With a little effort you should be able to show that my answer and 
the one from Doctor Roy are equivalent.

I came up with two more ways to derive the equation. Thinking about 
it in as many ways as possible is a good exercise.

1. Shift the sequence by substracting m-1 from every term. This 
gives you a sequence from 1 to n-m+1. You know how to get the sum 
for that sequence, so compute it and then add (n-m+1)*(m-1) which is 
the total for all of the shifts. A little manipulation will get you 
to the final form.

2. Here is my favorite solution. Just write down the answer! How? 
Look at it carefully.

              SUM = (n - m + 1)(n + m) / 2

Can you see that this is just the number of terms in the sequence 
times the average of the terms? Isn't that cool?

3. Thinking of the sum as the number of terms times the average of 
the terms will work just as well for sequences with any spacing. For 
a little challenge, see if you can add all of the odd integers from 
1 to 99 in your head.

Write again if you need more help.

- Doctor George, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 07/21/2003 at 01:54:49
From: Jamie Bruce
Subject: Thank you (Generalized Gauss Sum)

Thank you very much for your help. Your solution was very well laid 
out. I was thinking the sum was (m+n)(|m-n|+)/2 but can see now that 
the absolute value was not necessary, this also makes it much easier 
to prove by induction!