Closed form for this sum?
in [Math]
|
From: Jon Slaughter on 3 Dec 2009 05:45 Ostap S. B. M. Bender Jr. wrote: > On Dec 2, 6:57 pm, "Jon Slaughter" <Jon_Slaugh...(a)Hotmail.com> wrote: >> mike3 wrote: >>> On Dec 2, 1:37 pm, "Jon Slaughter" <Jon_Slaugh...(a)Hotmail.com> >>> wrote: >>>> mike3 wrote: >>>>> Hi. >> >>>>> Is there a closed form for >> >>>>> sum_{k=0...n-1} k^p exp(qk) >> >>>>> with p, q nonnegative integers? >> >>>>> Like how Faulhaber's formula gives a closed form for >>>>> sum_{k=0...n-1} k^p? I tried the "summation by parts" method but >>>>> it gives a nasty looking recurrence formula that I would not be >>>>> at all sure how to reduce to a "closed form". >> >>>> it's the same as >> >>>> d^p/dq^p sum(exp(qk)) >> >>>> since >> >>>> d^p/dq^p(exp(qk)) = k^p exp(qk) >> >>>> sum(exp(qk)) is known. >> >>> So since >> >>> sum_{k=0...n-1} exp(qk) = (exp(qn) - 1)/(exp(q) - 1) >> >>> then we have (for q > 0 -- for q = 0 we use Faulhaber's formula) >> >>> sum_{k=0...n-1} k^p exp(qk) = d^p/dx^p (exp(xn) - 1)/(exp(x) - 1) >>> eval'd at x=q. >> >>> But how do you expand that derivative for arbitrary orders p? >>> Wouldn't you need Faa di Bruno's formula to do it? Doesn't that >>> mean the expression grows extraordinarily quickly in length as >>> p goes up (grows up like the partition function(!)), or is there >>> some way it simplifies? >> >> Closed form simply means a finite number of computable operations >> that may include some standard non-closes quantities such as the >> trig functions. >> >> Your original sum is in closed form already. >> > > Really? So, there is no sense in asking for a "closed form solution" > to any sequence of partial sums? > > That makes taking many math exams much easier. For example, when your > 6th grade teacher asks you to find the closed-form solution to the > arithmetic progression sum S_n = sum_{k=0...n-1} k, just tell him that > it is already in closed-form. Exactly. What you guys are confusing is the different between a close form and non-closed form and that of a transformed form or a simpiler form. sum(x^k/k!,k=0..oo) is not a closed form. exp(x) is a closed form of the above series. Why? because exp is so common we take it to be closed(technically it is not because to compute exp(x) arbitrarily we must approximate it) Close forms started out as simply finitely computable things. Hence when people didn't know about exp(x) they were looking for finite ways to compute it. As time passed they realized there was no finite way. They then make a symbol for it(called it exp) and realized it was very useful. It showed up in so many different formulas that they decided to allow it to be counted as what is called an "elementary function". http://en.wikipedia.org/wiki/Elementary_function While exp(x) is not finitely computable there were enough tables to enough digits for it to essentialy be quasi computable. Now days the put is moot since we have computers and everything is quasi-computable(well, almost everything... ok, actually most things aren't...). Look at the wiki page... erf is not elementary but exp is? Why? Whats the difference? Both take an infinite amount of time to compute exactly(for arbitrary arguments of course). "In mathematics, an elementary function is a function built from a finite number of exponentials, logarithms, constants, one variable, and nth roots through composition and combinations using the four elementary operations (+ � � �). By allowing these functions (and constants) to be complex numbers, trigonometric functions and their inverses are included in the elementary functions (see Trigonometric function#Relationship to exponential function and complex numbers)." Hence the above sum from mike3 is an elementary function, is it not? "In mathematics, an expression is said to be a closed-form expression if, and only if, it can be expressed analytically in terms of a bounded number of certain "well-known" functions. Typically, these well-known functions are defined to be elementary functions; so infinite series, limits, and continued fractions are not permitted." Surely if you have any clue about mathematics you understand that the two above quoted statements prove that the original sum given by mike3 is already in closed form. Hence you simply have a misconception about what a closed form is. The majority of pure mathematics is exactly trying to reduce non-elementary and non-closed form expressions to those of elementary and closed. It's less of a problem today as it was 200 years ago but thats besides the point.
From: David W. Cantrell on 3 Dec 2009 10:34 "Jon Slaughter" <Jon_Slaughter(a)Hotmail.com> wrote: > David W. Cantrell wrote: > > mike3 <mike4ty4(a)yahoo.com> wrote: > >> Hi. > >> > >> Is there a closed form for > >> > >> sum_{k=0...n-1} k^p exp(qk) > >> > >> with p, q nonnegative integers? > >> > >> Like how Faulhaber's formula gives a closed form for sum_{k=0...n-1} > >> k^p? I tried the "summation by parts" method but it gives a nasty > >> looking recurrence formula that I would not be at all sure how to > >> reduce to a "closed form". > > > > Mathematica gives > > > > PolyLog[-p, E^q] - E^(q n) LerchPhi[E^q, -p, n] > > > > as a closed form for your sum. > > > > This is not a closed-form. As far as Mathematica is concerned, it is in closed form. (Also note Tim Little's reply on this matter.) > > BTW, Jon Slaughter seemed to think that your original expression was > > already in closed form, in part because it has only finitely many > > terms. But AFAIK according to most definitions of "closed form", the > > finite number of terms should be _bounded_. Your original sum has n > > terms. Since that number of terms is not bounded, I would say that > > your original expression is not already in closed form. > > You seem to think that it's simply the number of terms that make an > expression closed-form or not. Certainly not. Why did you think that I said "in part" above? The fact that the number of terms must be bounded is just one of several criteria. > This is not the case. Any finite sum is a closed form. No. It is not even true that any finite sum of terms involving only elementary functions is a closed form. > Any infinite sum is not. True. > Now, the distinction is actually > more complex since any finite sum can be "thought" of as an infinite sum. > > For example > > sum(delta(k),k=0..infinity) is actually a closed form expression. No. > It is identically 1 and simply a notational. A closed form for that infinite sum is 1, but the infinite sum itself is not a closed form. > Just because you can write symbolically an expression in simple form does > not mean it is closed. Of course. > Your expression above is not closed form because > the individual terms is not closed form. It is in closed form if LerchPhi and PolyLog are allowed. > Else, why not just define his original sum as q_DWC_p(n) and then respond > with "The closed form is q_DWC_p(n)"? Reason: Because q_DWC_p(n) is not a well-known function. It does not appear in the mathematical literature, computer algebra systems do not implement it, etc. > http://en.wikipedia.org/wiki/Closed-form_expression That's not really a very good reference. But if you had read it carefully, you should have noticed that it allows the possibility of admitting certain special functions as being "well known". > Why is his sum closed form already? Because it is a finite number > elementary terms. No. > Sure his formula depends on n and n grows without bound > but that has nothing to do with it. Yes it does, because the number of terms in the original sum is not bounded. > Your formula depends on n and grows > without bound on n too but yet you called it a closed form. The formula given by Mathematica has, regardless of n, just two terms. [snip] > Now, if you want to convince me I'm wrong then explain to me why your > answer given is 1. closed form, and 2. bounded in n. That's all been addressed earlier. To convince you that you're wrong about the original sum being already in closed form, I will quote from page 7 of the classic text _Concrete Mathematics_ by Graham, Knuth and Patashnik: "Sums like 1 + 2 + ... + n are not in closed form -- they cheat by using '...'; but expressions like n(n + 1)/2 are. We could give a rough definition like this: An expression for a quantity f(n) is in closed form if we can compute it using at most a fixed number of "well known" standard operations, independent of n." Thus, the reason that the original sum was not already in closed form is that the required number of additions depends on n. BTW, I had said above that the Wikipedia reference was not really very good. Here's an example of its shortcomings. Its second sentence is "Typically, these well-known functions are defined to be elementary functions; so infinite series, limits, and continued fractions are not permitted." Well, of course, I agree that infinitary operations are to be excluded. But saying that the well-known functions are _typically_ just the elementary ones is wrong. I think you would be hard pressed to find many mathematicians who would not allow, say, the floor function to be used in a closed form. David
From: mike3 on 3 Dec 2009 15:30 On Dec 3, 8:34 am, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote: > "Jon Slaughter" <Jon_Slaugh...(a)Hotmail.com> wrote: > > David W. Cantrell wrote: > > > mike3 <mike4...(a)yahoo.com> wrote: > > >> Hi. > > > >> Is there a closed form for > > > >> sum_{k=0...n-1} k^p exp(qk) > > > >> with p, q nonnegative integers? > > > >> Like how Faulhaber's formula gives a closed form for sum_{k=0...n-1} > > >> k^p? I tried the "summation by parts" method but it gives a nasty > > >> looking recurrence formula that I would not be at all sure how to > > >> reduce to a "closed form". > > > > Mathematica gives > > > > PolyLog[-p, E^q] - E^(q n) LerchPhi[E^q, -p, n] > > > > as a closed form for your sum. > > > This is not a closed-form. > > As far as Mathematica is concerned, it is in closed form. (Also note Tim > Little's reply on this matter.) > It is a closed form, but it's not in elementary functions. I want elementary functions, more specifically, combinations of other terms of the form x^r exp(sx) (times a coefficient, of course) for nonnegative integer r and s, when p and q are nonnegative integers. Just like how Faulhaber's formula sums x^p (p = nonnegative integer) in terms of other terms of the form x^r (r = nonnegative integer). That is, what you get from applying summation by parts, but in a non- recurrence form (even if the number of terms depends on p). Note that if you apply summation by parts, you get a crazy recurrence formula (derivation steps omitted, it was messy and YES, I worked this out by HAND) F(p, q, n) = 1/(exp(q) 1) * [n^p (exp(qn) 1) - sum_{j=1...p} C_(p, j) (exp(q) F(p-j, q, n) Fh(p-j, n))] where Fh(p, n) = sum_{k=0...n-1} k^p = 1/(p+1) sum_{k=0...p} C_(p+1,k) B_k n^(p+1-k) is Faulhaber's formula. Note that the sum starts at j-1, so this does reduce p by one on each recursion, and of course at p = 0 we have F(p, q, n) = (exp(qn) - 1)/(exp(q) - 1) and the recursion terminates there. Note that when expanded for a given p, this formula gives a solution that meets the requirements, the only trouble is it's a recurrence, and a nasty one at that, for general p. What could be done to get a non-recurrence version (even if we have a sum in it whose number of terms depends on p) with elementary functions of the form mentioned?
From: Jon Slaughter on 3 Dec 2009 16:45 David W. Cantrell wrote: > "Jon Slaughter" <Jon_Slaughter(a)Hotmail.com> wrote: >> David W. Cantrell wrote: >>> mike3 <mike4ty4(a)yahoo.com> wrote: >>>> Hi. >>>> >>>> Is there a closed form for >>>> >>>> sum_{k=0...n-1} k^p exp(qk) >>>> >>>> with p, q nonnegative integers? >>>> >>>> Like how Faulhaber's formula gives a closed form for >>>> sum_{k=0...n-1} k^p? I tried the "summation by parts" method but >>>> it gives a nasty looking recurrence formula that I would not be at >>>> all sure how to reduce to a "closed form". >>> >>> Mathematica gives >>> >>> PolyLog[-p, E^q] - E^(q n) LerchPhi[E^q, -p, n] >>> >>> as a closed form for your sum. >>> >> >> This is not a closed-form. > > As far as Mathematica is concerned, it is in closed form. (Also note > Tim Little's reply on this matter.) > ? Are you saying just because mathematica returned a result it must be in closed form? >>> BTW, Jon Slaughter seemed to think that your original expression was >>> already in closed form, in part because it has only finitely many >>> terms. But AFAIK according to most definitions of "closed form", the >>> finite number of terms should be _bounded_. Your original sum has n >>> terms. Since that number of terms is not bounded, I would say that >>> your original expression is not already in closed form. >> >> You seem to think that it's simply the number of terms that make an >> expression closed-form or not. > > Certainly not. Why did you think that I said "in part" above? The > fact that the number of terms must be bounded is just one of several > criteria. > So sum(k,k=1..n) is unbounded in n but n*(n+1)/2 is not? >> This is not the case. Any finite sum is a closed form. > > No. It is not even true that any finite sum of terms involving only > elementary functions is a closed form. > Right, thats what I meant to say(well, what I had in mind) ;) >> Any infinite sum is not. > > True. > >> Now, the distinction is actually >> more complex since any finite sum can be "thought" of as an infinite >> sum. >> >> For example >> >> sum(delta(k),k=0..infinity) is actually a closed form expression. > > No. > >> It is identically 1 and simply a notational. > > A closed form for that infinite sum is 1, but the infinite sum itself > is not a closed form. > In this case they are identical. Your logic says that if sum(a_k,k=0..n) is in closed form but it is well known that a_k = 0 for all k > n then writing sum(a_k, k=0..oo) Is going to make it a non-closed form? >> Just because you can write symbolically an expression in simple form >> does not mean it is closed. > > Of course. Then why do you agree with what you said above? > >> Your expression above is not closed form because >> the individual terms is not closed form. > > It is in closed form if LerchPhi and PolyLog are allowed. True. If you want to take them as elementary. Now, this is somewhat artificial and origially wasn't like this. The elementary functions were simply those that were computable. What closed form origially meant was something that someone could go out and compute by hand. Like 3 + 4 + 9 + 2 is closed because it can be computed exactly in a finite amount of time. sum(k,k=0..n) = n*(n+1)/2 the rhs is simply another representation. One that is simpler. Both are closed. If not the the only different is the number of terms. True, sum(k,k=0..n) is unbounded in the number of terms while n*(n+1)/2 is always just 2. But that obviously isn't the only criteria. I agree that the rhs is simpler than the left. One might say it is more "closed" than not. But from all the "definitions" I've seen of closed only require a finite number of terms of elementary functions which is exactly what the lhs is. > >> Else, why not just define his original sum as q_DWC_p(n) and then >> respond with "The closed form is q_DWC_p(n)"? > > Reason: Because q_DWC_p(n) is not a well-known function. It does not > appear in the mathematical literature, computer algebra systems do > not implement it, etc. > >> http://en.wikipedia.org/wiki/Closed-form_expression > > That's not really a very good reference. But if you had read it > carefully, you should have noticed that it allows the possibility of > admitting certain special functions as being "well known". Um... you mean thinks like exp(x), cos(y), etc..? Like things we called elementary functions? http://en.wikipedia.org/wiki/Elementary_functions No mention in there of LerchPhi... > >> Why is his sum closed form already? Because it is a finite number >> elementary terms. > > No. > >> Sure his formula depends on n and n grows without bound >> but that has nothing to do with it. > > Yes it does, because the number of terms in the original sum is not > bounded. Yes, thats what I just said. >> Your formula depends on n and grows >> without bound on n too but yet you called it a closed form. > > The formula given by Mathematica has, regardless of n, just two terms. Ok, I see... your definition of closed form is anything returned by Mathematica. Now it makes sense. Sorry for the confusion. We just have two completely different definitions of the same term. > > [snip] >> Now, if you want to convince me I'm wrong then explain to me why your >> answer given is 1. closed form, and 2. bounded in n. > > That's all been addressed earlier. > > To convince you that you're wrong about the original sum being > already in closed form, I will quote from page 7 of the classic text > _Concrete Mathematics_ by Graham, Knuth and Patashnik: > > "Sums like 1 + 2 + ... + n are not in closed form -- they cheat by > using '...'; but expressions like n(n + 1)/2 are. We could give a > rough definition like this: An expression for a quantity f(n) is in > closed form if we can compute it using at most a fixed number of > "well known" standard operations, independent of n." > > Thus, the reason that the original sum was not already in closed form > is that the required number of additions depends on n. > > BTW, I had said above that the Wikipedia reference was not really very > good. Here's an example of its shortcomings. Its second sentence is > "Typically, these well-known functions are defined to be elementary > functions; so infinite series, limits, and continued fractions are not > permitted." Well, of course, I agree that infinitary operations are > to be excluded. But saying that the well-known functions are > _typically_ just the elementary ones is wrong. I think you would be > hard pressed to find many mathematicians who would not allow, say, > the floor function to be used in a closed form. > Ok, then there is another definition of closed form. Yet his definition then contradicts the use of using non-closed expressions in closed expressions. You are right though. If we define closed form as "An expression dependent on a variable is in closed form if the number of terms do not grow unbounded as that variable does and composed of only a finite number of elementary symbolic functions." hence exp(x) is a closed form representation in x. sum(x^k/k!,k=0..oo) is a closed form representation in x but not k. sum(k,k=1..n) is not a closed form representation in n but is in k. (after all, the number of terms does not grow when k changes). n*(n+1)/2 is a closed form representation in n. Hence exp(x) is thought simply as a symbol rather than any concrete representation and because it is common enough it is considered "elementary". LerchPhi[x] then is also a symbolic function yet may or may not be elementary. So such definitions follows your line of though. My definition does not. While I have no issues of limiting the growth of the number of terms as it does seem better I do have issues with calling any function that mathematica returns as elementary. We could simply say "An elementary function is anything symbolically returned by Mathematica". Now you just need to petition to add q_DWC_p(n) to their database so it is then elementary. For me elementary means something just that... it is elementary. Now elementary is relative my dear Cantrell. But does there not come a point when everything is called elementary? You say " It does not > appear in the mathematical literature, computer algebra systems do > not implement it, etc." So is your criteria for elementary functions simply that they are democratically elected? Surely you understand then it would be impossible for such functions to exist? Surely we can agree that exp(x) is much more elementary than Lerchphi? I think maybe, but not sure if it works well, that a criteria for elementary function is an expression that is not similar to any other elementary function through elementary manipulations(which needs to be defined). Hence something like sum(x!/(k+1)!) is not elementary since it "resembles" exp(x) and exp(x). So one has actually an idea of "more elementary". It's pretty vague though and would be nice if there were a more precise definition that made a bit more sense. Lerchphi is a "generalization" of the zeta function and hence the zeta function seems more elementary. Hence, because the Lerchphi function seems like a "direct" generalization it seems less elementary. I imagine if someone actually worked on it they could come up with a decent theory of closed form expressions that encompesses the ideas we are discussing and is useful. After all, one could just define a function like sum(k^(an)*x^(bk)/(ck)!/k^d*Cr(m, e*k)*B_(f*k)(y)*exp(z*k)) This expression contains most of our major mathematical functions simple and natural way. If there's one thats not in there I can easily add it if you want. This function is much more useful than simply exp(x) or zeta(d) alone? If mathematica just added it surely it would be useful? But do you really think it is elementary?
From: Tim Little on 3 Dec 2009 19:34
On 2009-12-03, Jon Slaughter <Jon_Slaughter(a)Hotmail.com> wrote: > LerchPhi is an infinite series... So is nearly everything else, including functions like f(x) = 1/(1-x), which can be expressed as an analytic extension of the power series f(x) = sum_(k=0 to inf) x^k. > So you can call it closed if you want... it's up to you. I agree it is > relative but you are streching the truth a lot if you think that it is > useful in closed forms. It is quite useful as a closed form. A lot is known about that function, so that it can be manipulated symbolically much more easily than by treating it generically as an instance of a power series. > Finite sums of simple things like exponential and cos functions, > sqrt's, etc are more "closed" than things involving infinite sums? How are you defining "simple" things like exponential and cos functions that do not involve infinite sums? Probably the most common definition of e^x is by the power series e^x = Sum_(k=0 to inf) x^k/k!. Other definitions include limits of infinite sequences such as (1+1/n)^n, or as a solution to an integral equation or differential equation - both of which also involve limits. Apart from familiarity, why do you call this a "simple" thing while LerchPhi is not? - Tim |