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.)
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.)
Assuming I interpreted your notation correctly, Maple gives:
where GAMMA(n) = (n-1)!.
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)!.
This is very easy to derive (and prove) using finite calculus: Check out e.g.
http://www.stanford.edu/~dgleich/publications/finite-calculus.pdf
http://www.stanford.edu/~dgleich/publications/finite-calculus.pdf
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
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
Yeah. Like mathematicians love to say: "Demonstration is left to the reader as an exercise"!
:D
:D
Bleh
Did you miss your basic calculus class? :(
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 :)
E = mc²
Thank you very much!
xernobyl: I'm not a math student...
ryg: of course it's overkill, i just wanted to raise awareness: hypergeometric sums are the "big picture" point of view.
Quote:
I discovered today..
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!