pouët.net

Go to bottom

Summation formulas

category: offtopic [glöplog]
 
You probably know this from school:

1 + 2 + 3 + ... + n = (n + 1) * n / 2

I discovered today that apparently similar approaches work for the following summations:

1 * 2 + 2 * 3 + 3 * 4 + ... + (n - 1) * n = (n + 1) * n * (n - 1) / 3

1 * 2 * 3 + 2 * 3 * 4 + 3 * 4 * 5 + ... + (n - 2) * (n - 1) * n = (n + 1) * n * (n - 1) * (n - 2) / 4

And so on.

Every single equation can probably be proven by mathematical induction, but is there a way to prove it for the general case? That is:

Sum i = 1 to n - k + 1 of Product j = 0 to (k - 1) of (i + j) = 1 / (k + 1) * Product i = 1 to (k + 1) of (n + 2 - i)

(I hope I didn't make a calculation mistake.)
added on the 2010-11-06 17:11:16 by Adok Adok
Assuming I interpreted your notation correctly, Maple gives:

Code: > sum(product(i + j, j=1..k-1), i=1..n-k+1); (n - k + 2) GAMMA(n + 2) GAMMA(1 + k) ------------------------ - ------------ k GAMMA(n - k + 3) k

where GAMMA(n) = (n-1)!.
added on the 2010-11-06 17:42:39 by Sesse Sesse
This is very easy to derive (and prove) using finite calculus: Check out e.g.
http://www.stanford.edu/~dgleich/publications/finite-calculus.pdf
added on the 2010-11-06 18:54:46 by ryg ryg
When the ratio of consecutive terms in a series or sum is a rational function of the index, the series (sum) is called hypergeometric. In your examples, this rational function is k/(k-1), (k+1)/(k-1), and (k+2)/(k-1); of course, you may shift k by a finite number, depending on where you start indexing the terms. But if you have for example a sum with binomial terms, that usually also falls into this category.

Hypergeometric sums are pretty well understood: there are algorithms which can decide whether the sum has a closed form, and also give the closed form when it exists (and also a proof of it, though not in the usual sense of proof). That's how Maple/Mathematica computes these sums.

A (free) introductory book on this is titled "A=B", http://www.math.upenn.edu/~wilf/AeqB.html
added on the 2010-11-06 19:07:48 by blala blala
Yeah. Like mathematicians love to say: "Demonstration is left to the reader as an exercise"!
:D
added on the 2010-11-06 19:11:38 by RetroVM RetroVM
Bleh
added on the 2010-11-06 19:40:32 by texel texel
Did you miss your basic calculus class? :(
added on the 2010-11-06 19:43:06 by xernobyl xernobyl
blala: While dealing with this as a hypergeometric function works (and is the preferable solution for algorithmic approaches to the problem and in symbolic math packages such as Mathematica or Maple), using it to compute sums of falling factorials is complete overkill :)
added on the 2010-11-06 20:17:21 by ryg ryg
E = mc²
added on the 2010-11-06 21:53:05 by magic magic
Thank you very much!
added on the 2010-11-06 22:06:59 by Adok Adok
xernobyl: I'm not a math student...
added on the 2010-11-06 22:16:31 by Adok Adok
ryg: of course it's overkill, i just wanted to raise awareness: hypergeometric sums are the "big picture" point of view.
added on the 2010-11-07 12:48:26 by blala blala
Quote:

I discovered today..
added on the 2010-11-07 13:21:49 by v3nom v3nom
ryg: The document you linked was very interesting and helpful. After reading the first six pages, I knew how the theorem can be proven. Thank you very much!
added on the 2010-11-07 20:22:04 by Adok Adok

login

Go to top