From: David Case Newsgroups: sci.math Subject: Sigma function Date: Sat, 03 May 1997 02:43:17 +0000 Organization: School of Music, University of Oregon Lines: 79 Reply-To: davecase@oregon.uoregon.edu While taking high school calculus I began looking for a general polynomial solution to: i Sum k^n for positive integers i and n k=1 The solution I eventually found was quite a bit more general and is what I call the Sigma function, evaluable for real x and non-negative integers n and d: 1 n-1 Sigma(x,n,d) = - * Sum C(n-k,k+1)*P(x-k,d), d! k=0 d-1 where P(x,d) = Prod x+k k=0 and C(n,k) = if (n = 1) or (k = 1) then 1 else n*C(n,k-1)+k*C(n-1,k) The C (coefficient) function is recursively related to Pascal's triangle and sums to n! as follows: n-1 n! = Sum C(n-k,k+1) k=0 What the Sigma function calculates is described below - n! = Sigma(x,n,0) nCr(n,r) = Sigma(n-r+1,1,r) x^n = Sigma(x,n,n) a Sum k^n = Sigma(a,n,n+1) - the solution to the original problem k=1 In general, for any positive integer n, if p[n](a) = the polynomial a^n and p[d](a) = the series of related polynomials: p[0](a) = p[1](a) - p[1](a-1) = n!, p[1](a) = p[2](a) - p[2](a-1), p[2](a) = p[3](a) - p[3](a-1), . . p[n](a) = p(a) = a^n, p[n+1](a) = the polynomial that sums p[n] over [1, a], p[n+2](a) = the polynomial that sums p[n+1] over [1, a], . . p[d](a) = the polynomial that sums p[d-1] over [1, a], then Sigma(x,n,d) = p[d](x). Well, after that rather long introduction what I want to know is: (1) Has anyone ever heard of this result before, and if so, who was the original discoverer? I once asked a retired professor at my school if he had heard of it. He thought that the result was derived sometime in the last century, but he couldn't remember who the discoverer was. (2) Can anyone find a closed form for the C(n,k) coefficients? The double recursion gets 'expensive' for large n, so a closed form would be nice, if one is possible. (3) Does this result have any relevance elsewhere, FLT perhaps? Thanks, Dave Case * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Willi Moehring Willi Moehring wrote: > > This problem was solved by James Bernoulli and published in 1713. You > can find > a description of the solution as Bernoulli's theorem in Ch. XXIII > > of G. Chrystal, Textbook of Algebra, Vol. 2 > > Willi Willi - * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Thanks, I found Chrystal's book (2nd edition, pub. 1900!) at the library. Bernoulli's i Theorem covers the original problem, Sum k^n, but doesn't cover the general solution k=1 that I found. There are other differences, Bernoulli's solution uses the Bernoulli numbers and contains alternating signs, mine makes use of neither of those directly. I also couldn't find any reference to the C(n,k) coefficients in Chrystal or on the Web. The first few of these coefficients are listed below. The sum of kth diagonal (up and to the right) is k! | n | C(n,k) | 1 2 3 4 5 6 7 8 9 ________|_______________________________________________________________________ | k 1 | 1 1 1 1 1 1 1 1 1 | | 2 | 1 4 11 26 57 120 247 502 | | 3 | 1 11 66 302 1191 4293 14608 | | 4 | 1 26 302 2416 15619 88234 | | 5 | 1 57 1191 15619 156190 | | 6 | 1 120 4293 88234 | n-1 | n! = Sum C(n-k,k+1) 7 | 1 247 14608 k=0 | | 8 | 1 502 | | 9 | 1 My general solution is related to the 'method of finite differences' mentioned in Chrystal. The table below gives the Sigma function for n = 3, evaluated at the integers a. The cubes appear at d = 3, the sums of the cubes appear at d = 4, the sums of the sums of the cubes at d = 5, etc., where d = the degree of the polynomial being evaluated. The entries in the table all follow the recurrence relation: Sigma(a,n,d) = Sigma(a-1,n,d) + Sigma(a,n,d-1). For integers the Sigma function can be expressed in terms of nCr: n-1 Sigma(a,n,d) = Sum C(n-k,k+1)*nCr(a+d-1-k,d). k=0 For the n = 3 case we have Sigma(a,3,d) = nCr(a+d-1,d) + 4*nCr(a+d-2,d) + nCr(a+d-3,d) | a | Sigma(a,3,d) | 0 1 2 3 4 5 6 7 8 ______________|____________________________________________________________ |d 0 | 6 6 6 6 6 6 6 6 | 1 | -6 0 6 12 18 24 30 36 42 | 2 | 1 1 7 19 37 61 91 127 169 | 3 | 0 1 8 27 64 125 216 343 512 | 4 | 0 1 9 36 100 225 441 784 1296 | 5 | 0 1 10 46 146 371 812 1596 2892 | 6 | 0 1 11 57 203 574 1386 2982 5874 | 7 | 0 1 12 69 272 846 2232 5214 11088 All the other cases of n work in the same fashion, so my solution is much more general than Bernoulli's which is just the case where d = n+1. Can you (or anyone) suggest somewhere else I might look to find the discoverer of the general result? Thanks again, Dave Case