Generalized Gauss SumDate: 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! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/