| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 996.1 | | AITG::DERAMO | Daniel V. {AITG,ZFC}:: D'Eramo | Tue Dec 20 1988 13:18 | 23 |
| It sounds like your "sum for a list of numbers" is
1 + 2 + 3 + ... + n = (1/2)n(n+1)
Are you asking about
2 2 2 2
1 + 2 + 3 + ... + n = ?
2 3 3 3
1 + 2 + 3 + ... + n = ?
etc.
Or maybe you wanted
2 3 n
1x + 2x + 3x + ... nx = ?
It wasn't clear to me what you were asking.
Dan
|
| 996.2 | An algorithm | SMURF::DIKE | | Tue Dec 20 1988 13:29 | 25 |
| There is no way (that I know of) to go from SUM(x^n) to SUM(x^(n+1)).
However, there is something that is almost as good:
SUM(x*(x+1)*(x+2)*...*(x+n-1)/n!) = x*(x+1)*(x+2)*...*(x+n)/(n+1)!
E.g. SUM(x) = x*(x+1)/2,
SUM(x*(x+1)/2) = x*(x+1)*(x+2)/6, etc.
You can use this to calculate SUM(x^n) the following procedure:
SUM(x*(x+1)*(x+2)*...*(x+n-1)/n!) = x*(x+1)*(x+2)*...*(x+n)/(n+1)!
Multiply out the argument to SUM to get a polynomial:
SUM(a*x^0 + b*x^1 + ... + c*x^n) = ...
Split the SUM apart:
a*SUM(x^0) + b*SUM(x^1) + ... + c*SUM(x^n) = ...
Substitute in the formulas for SUM(x^0) through SUM(x^(n-1)), which
you have conveniently already calulated :-) and solve for SUM(x^n).
Unfortunately, this requires the calulation of SUM(x^i) for
i < n. I don't know of any way to calculate it directly.
Jeff
|
| 996.3 | | ALIEN::POSTPISCHIL | Always mount a scratch monkey. | Tue Dec 20 1988 14:11 | 42 |
| Re .0:
Suppose there is a formula in the form ax^3 + bx^2 + cx + d that gives
you the sum of 1^2 + 2^2 + 3^2 + 4^2 + . . . + x^2. That last sum can
also be written as the sum for i from 1 to x of i^2, and for
simplicity, I will write sum^2(x).
Well, the difference between sum^2(x+1) and sum^2(x) is just (x+1)^2,
since that is the next term in the series.
So [a(x+1)^3 + b(x+1)^2 + c(x+1) + d] - [ax^3 + bx^2 + cx + d] =
(x+1)^2. Expand to get:
a(x^3+3x^2+3x+1 - x^3) + b(x^2+2x+1 - x^2) +c(x+1 - x) + d(1-1) =
x^2+2x+1.
Simplify a bit: a(3x^2+3x+1) + b(2x+1) + c = x^2 + 2x + 1.
Now this has to be true for every x. That means we can separate the
powers of x in the above equation to get three equations. E.g.,
if x is 0, we have:
a+b+c = 1.
Using that and other values for x, we can figure:
3ax+2bx = 2x, so 3a+2b = 2, and
3ax^2 = x^2, so 3a = 1.
Therefore, a = 1/3, b = 1/2, and c = 1/6. All we need is d. When
there are zero terms in the series, we want the sum to be zero, so 0 =
ax^3+bx^2+cx+d = d when x is 0.
Therefore, sum^2(x) = (1/3)x^3 + (1/2)x^2 + (1/6)x. You can put
this over a common denominator for a better appearance:
sum^2(x) = (2x^3 + 3x^2 + x)/6.
Sums of cubes can be done in the same manner.
-- edp
|
| 996.4 | An answer, of sorts... | SSDEVO::LARY | One more thin gypsy thief | Tue Dec 20 1988 15:11 | 25 |
| I'm sure this is not what you need, but...
A semi-closed form (out of "Summation of Series") for
sum(i^k) from i=1 to i=n is:
[k/2]
k+1 k ------ i k+1-2i
(n+1) (n+1) \ (-1) k! (n+1) zeta(2i)
------- - ------ - 2 * > ----------------------------
k+1 2 / 2i
------ (k-2i)! (2*pi)
i = 1
where zeta(j) is the Riemann Zeta function,
infinity
----- 2 4
\ 1 pi pi
zeta(j) = > --- E.G. zeta(2) = ------, zeta(4) = ------
/ j 6 90
----- i
i = 1
Pretty horrible, eh? I'd rather solve the simultaneous equations of .-1...
|
| 996.5 | briefly,... | PTERA::YARBROUGH | | Tue Dec 20 1988 16:27 | 5 |
| sum(i^2,i=1..n) = (2n^3+3n^2+1)/6
sum(i^3,i=1..n) = (n^4+2n^3+n^2)/4
Enjoy the puzzles! - Lynn
|
| 996.6 | what a coincidence! :-) | AITG::DERAMO | Daniel V. {AITG,ZFC}:: D'Eramo | Tue Dec 20 1988 17:28 | 11 |
| A nice one is
3 3 3 2
1 + 2 + ... n = (1 + 2 + ... + n)
Or, in the notation of .5,
2
sum(i^3, i = 1,...,n) = sum(i, i = 1,...,n)
Dan
|
| 996.7 | | HPSTEK::XIA | | Tue Dec 20 1988 20:51 | 44 |
| The problem was solved by Jacob Bernoulli in the 17th century. The
method is recursive.
Find the sum 1^p + 2^p + ... + n^p.
Step 0: Let G = 1/2.
1
Step 1: Rewrite the equation (x - 1)^p - x^p = 0 as a polynomial
f(x) = a * x^(p-1) + a * x^(p-2) + ... = 0
p-1. p-2
Step 2: Let G = (a * G + a * G + .....) / a
p-1 p-2 p-2 p-3 p-3 p-1
Step 3: Let g(x) = (n + x)^(p+1) - x^(p+1).
Rewrite the function as:
h(x) = a * x^(p) + a * x^(p-1) + ....
p p-1
Then 1^p + 2^p + ... + n^p = (a * G + * G + ...) / (p+1)
p p p-1 p-1
Of course, in this age of computer, the best way to do it is the
undetermined coefficient method (I proudly announce that I
independently discovered this method while in Junor high :-) :-).
Solve the matrix equation for a0...ap+1:
1^p = a0 + a1 + a2 + ... + ap+1
1^p + 2^p = a0 + a1 * 2 + a2 * 2^3 + ... + ap+1 * 2^(p+1)
1^p + 2^p + 3^p = a0 + a1 * 3 + a2 * 3^3 + ... + ap+1 * 3^(p+1)
.
.
.
1^p + 2^p + ... + (p+2)^p = a0 + a1 * (p+2) +...+ ap+1 * (p+2)^(p+1)
I am not sure whether the matrix can ever go singular, but if it
does, just collect another equation by adding more terms to the
series.
Eugene
|
| 996.8 | Thanks | IOSG::HOPKINS | King of the Vids | Thu Dec 22 1988 12:00 | 7 |
| Thank you for all your help. I have solved the puzzle and also
enjoyed trying to work through some of these hyper-complex methods
for finding the answer.
Thanks Again,
Greg
|
| 996.9 | | KOBAL::GILBERT | Ownership Obligates | Fri Dec 23 1988 18:47 | 88 |
| n p
Define f (n) = Sum k . Now f (n) is a polynomial of degree p+1 in n, so
p k=0 p
p+1 k
for a particular p, define the coefficients a by f (n) = Sum a n .
k p k=0 k
p k k i k k-i
Now f (n) - f (n-1) = n , and since (n-1) = Sum (-1) ( ) n (by the
p p i=0 i
p+1 k i k k-i
binomial theorem), we have f (n-1) = Sum a Sum (-1) ( ) n . Exchanging
p k=1 k i=0 i
p+1 k p+1 j-k j
the order of the summation, f (n-1) = Sum n Sum a (-1) ( ), and so
p k=0 j=k j k
p+1 k p+1 j-k j p
f (n) - f (n-1) = Sum n ( a - Sum a (-1) ( ) ) = n . This simplifies
p p k=0 k j=k j k
p+1 k p+1 j-k j p
slightly to Sum n Sum a (-1) ( ) = - n . We will equate like powers
k=0 j=k+1 j k
1
of n, and solve for the a . First, we see that a = ---, and for 0 <= k < p,
j p+1 p+1
p+1 j-k j 1 p
Sum a (-1) ( ) = 0. Continuing, we an find that a = -, a = ---,
j=k+1 j k p 2 p-1 12
p(p-1)(p-2)
a = 0, a = - -----------, .... This suggests the substitution:
p-2 p-3 720
p+1
a = b ( ) / (p+1). Thus, we have b = 1, and (for 0 <= k < p),
j p-j j -1
p+1 p+1 j-k j p+1 j p+1 p+1-k
Sum b ( ) (-1) ( ) / (p+1) = 0. But ( ) ( ) = ( ) ( ),
j=k+1 p-j j k j k p+1-k p+1-j
p+1
which can be substituted into the recurrence for the b . Now ( ) / (p+1)
p-j p+1-k
is independent of the summand, and can be factored from the recurrence, giving:
p+1 p+1-k j-k
Sum b ( ) (-1) = 0, (for 0 <= k < p). Changing variables, and
j=k+1 p-j p+1-j
m m+2 w
reversing the order of summation, we simply further: Sum b ( ) (-1) = 0,
w=-1 w w+1
m-1 m+2 m+1-w
so that we have: b = 1, and b = Sum b ( ) (-1) / (m+2), and note
-1 m w=-1 w w+1
that the b are independent of p.
m
p+1 p+1 k
Putting this together, we have f (n) = Sum b ( ) n / (p+1), where
p k=1 p-k k
the b are as given above.
m
The first several values of the b are: b = 1, b = 1/2, b = 1/6, b = 0,
m -1 0 1 2
b = -1/30, b = 0, b = 1/42, b = 0, b = -1/30, b = 0, and b = 5/66.
3 4 5 6 7 8 9
You'll note that these are suspiciously similar to the Bernoulli numbers.
- Gilbert
|
| 996.10 | | KOBAL::GILBERT | Ownership Obligates | Wed Dec 28 1988 13:01 | 64 |
| > You'll note that these are suspiciously similar to the Bernoulli numbers.
Indeed! In .-1, b = B + d , where B is the mth Bernoulli number,
n n+1 n,0 m
and d is Kronecker's delta (d = 1 if i = j; otherwise d = 0).
i,j i,j i,j
And so we have:
n p p p+1 k+1
Sum k = Sum (B + d ) ( ) n / (p+1)
k=0 k=0 p-k p-k,1 k+1
p p p+1 p-k+1
= n + Sum B ( ) n / (p+1)
k=0 k k
Or,
n-1 p p p+1 p-k+1
Sum k = Sum B ( ) n / (p+1)
k=0 k=0 k k
= = = = = = = = = =
See also problem 4 of section 1.2.11.2 in Knuth's "Art of Computer Programming",
where this result is derived from Euler's summation formula:
n-1 n m (k-1) (k-1)
Sum f(k) = Int f(x) dx + Sum B (f (n) - f (l))/k! + R ,
k=l l k=1 k m
where
m+1
(-1) n (m)
R = ------- Int B ({x}) f (x) dx,
m m! l m
m m m-k
B (x) is the Bernoulli polynomial: B (x) = Sum B ( ) x ,
m m k=0 k k
(n)
f (x) is the nth derivative of f(x), and {x} is the fractional part of x.
= = = = = = = = = =
Here's some interesting miscellany about the Bernoulli numbers.
The Bernoulli numbers may be defined by the recurrence:
n n
Sum ( ) B = B + d
k=0 k k n n,1
They are also the coefficients in the infinite series:
x inf k
------- = Sum B x / k!
x k=0 k
e - 1
And when r is an even integer,
inf r 1 r
Sum 1 / k = - |B | (2 pi) / r!
k=1 2 r
|
| 996.11 | summation made easy | ELWOOD::CHINNASWAMY | | Wed Mar 15 1989 14:40 | 24 |
| It is a long time since I looked into this conference. Here is a simple
solution ( I hope).
(n)
Let us define X = X(X -1)(X - 2) ... (X - n + 1)
3 (3) (2) (1)
Let X = X + a*X + b*X
It is easy to find the values of a and b by substituting X = 1, X = 2, etc,
a = 3, b = 1
Summation is like integration.
(4) (3) (2)
n (n + 1) (n + 1) (n + 1)
sum X = -------- + 3 * ------- + 1 * ------- + C
1 4 3 2
For n = 1, C = 0.
It is easy to extend this to higher powers. You don't have to solve simultaneous
equations.
|