Closed form for this sum?
in [Math]
|
From: mike3 on 2 Dec 2009 22:29 On Dec 2, 7:57 pm, "Jon Slaughter" <Jon_Slaugh...(a)Hotmail.com> wrote: <snip> Perhaps I wasn't clear... what I want is it written in explicit form without derivatives, just as a sum of terms dependent only on p and/or q and not on n. I.e. like how we can expand sums of powers with Faulhaber's formula (slightly different form as this sums from 0 to n-1 not 1 to n but still...): sum_{k=0...n-1} k^p = 1/(p+1) sum_{k=0...p} C_(p+1, k) B_k n^(p+1-k) = 1/(p+1) (B_(p+1)(n) - B_(p+1)(0)) where B_k are Bernoulli numbers, B_k(x) are Bernoulli polynomials, and "C" is the binomial coefficient function.
From: David W. Cantrell on 3 Dec 2009 00:00 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. 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. David
From: Jon Slaughter on 3 Dec 2009 03:11 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. > 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. This is not the case. Any finite sum is a closed form. Any infinite sum is not. 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. It is identically 1 and simply a notational. Just because you can write symbolically an expression in simple form does not mean it is closed. Your expression above is not closed form because the individual terms is not closed form. 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)"? http://en.wikipedia.org/wiki/Closed-form_expression Why is his sum closed form already? Because it is a finite number elementary terms. Sure his formula depends on n and n grows without bound but that has nothing to do with it. Your formula depends on n and grows without bound on n too but yet you called it a closed form. So I don't know what your definition of closed form is but it's definitely not one in the set of "most definitions". You seem to think, at least by the answer you gave, that simple symbol juggling is enough to produce closed form solutions. If that is the case then everything has a closed form solution because we can just make a new symbol for it's non-closed form expression. This is most definitely not the case. 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.
From: Ostap S. B. M. Bender Jr. on 3 Dec 2009 03:55 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. > > In fact, your sum is exactly > the exansion of what I gave. > > For example, suppose you were to expand several of the derivatives. You > would find that they are exactly sum_{k=0...n-1} k^p exp(qk). > > It may be that there are other possible expressions. The derivatives may > offer a different point of few for some other simplification. > > Your question is kinda like asking, > > "What is the closed form for 9/3x^2/x" > > Well, you have 18/6*x, (9x + x)/3 - 3x, and some fourier series and fourier > transform and many other representations... Which one do you want? >
From: mike3 on 3 Dec 2009 03:56
On Dec 2, 10:00 pm, David W. Cantrell <DWCantr...(a)sigmaxi.net> 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. > Can this be reduced to elementary functions if we fix p and q as nonnegative (or at least positive) integers and constant? As that's what I'm after. I.e. something like a sum from 0 to p or 0 to p-1 of something else, with all involved term numbers depending on only p and/or q and not n? If we use your "bounded number of terms" criterion for closed form, then this will be a closed form if these are fixed as constant, nonnegative integers, just as Faulhaber's formula gives a closed form when the p-parameter is fixed to a constant, nonnegative integer. > 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. > > David |