Closed form for this sum?
in [Math]
|
From: Tim Little on 3 Dec 2009 20:02 On 2009-12-03, Jon Slaughter <Jon_Slaughter(a)Hotmail.com> wrote: > 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. And 1/9 is not, because no matter how many 1s you put in 0.1111..., you'll never get exactly 1/9? Or if you don't like that example, how about sqrt(2)? Certainly the Pythagoreans thought there was a huge difference between it and 1/9. > exp(x) is a closed form representation in x. Yes. > sum(x^k/k!,k=0..oo) is a closed form representation in x but not k. The symbol k is not a variable of that expression; it makes no sense to evaluate the expression for different values of k. So it makes no sense to even ask whether it is a closed-form representation in k. It is not a closed form in x either, as the number of terms is infinite for all x. > 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. If some function is well-known enough to be worth the programming effort to build into a computer algebra system in worldwide use, I'd say it's at least reasonable to accept it as a closed form. > But does there not come a point when everything is called > elementary? No, because there are infinitely many functions, and at any point only finitely many can be considered elementary. > Surely we can agree that exp(x) is much more elementary than > Lerchphi? Yes, I can accept that. The exponential function is known to pretty much everyone who passed high school mathematics. > 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). I think that does not work well. If sin(x) is elementary, then cos(x) would be necessarily not elementary. Likewise for exp(x). > 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. It doesn't even appear to make syntactic sense. What are the symbols over which you are summing, and what are the parameters of the function? Is "e" Euler's constant, or a (possibly integer) fifth parameter? > 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? I have no idea what properties that function would have or how it would be symbolically related to any other functions for various parameter values. Why would it be surely much more useful? As far as I can tell, I have never encountered an expression in my mathematical work that would be simplified by the use of that function. Unlike LerchPhi. - Tim
From: Ostap S. B. M. Bender Jr. on 3 Dec 2009 20:37 On Dec 3, 2:45 am, "Jon Slaughter" <Jon_Slaugh...(a)Hotmail.com> wrote: > 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. > Well, when "we guys" say "closed form", we mean something that doesn't include the term "sum" or a substring like "...". Thus, to "us guys" the formula sum_{k=0...n-1} k is not "closed term". However, n*(n-1)/2 is closed-term. > > 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: Ostap S. B. M. Bender Jr. on 3 Dec 2009 20:45 On Dec 3, 5:37 pm, "Ostap S. B. M. Bender Jr." <ostap_bender_1...(a)hotmail.com> wrote: > On Dec 3, 2:45 am, "Jon Slaughter" <Jon_Slaugh...(a)Hotmail.com> wrote: > > > > > 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. > > Well, when "we guys" say "closed form", we mean something that doesn't > include the term "sum" or a substring like "...". Thus, to "us guys" > the formula > > sum_{k=0...n-1} k > > is not "closed term". > > However, n*(n-1)/2 is closed-term. > I meant "closed-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: Zdislav V. Kovarik on 3 Dec 2009 20:57 On Thu, 3 Dec 2009, Jon Slaughter 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? > >> I lost the other replies (not coming frequently to this group), but I recall someone used repeated derivatives by a parameter. I have another solution, using difference calculus instead of differential calculus. I can re-phrase and extend the problem by asking for a closed form for the sum P(0) + r*P(1) + r^2*P(2) + ... + r^(n-1)*P(n-1), explained in a moment. For a polynomial P(x) of degree D or less, define the repeated forward differences Delta^0 P(x) = P(x); Delta^(k+1) P(x) = Delta^k (P(x+1)-P(x)) Observe that Delta^(D+1) P(x) = 0 (constant). Now the "summing" function f(n,r) (n non-negative integer, r different from 1) is defined as f(n,r) = sum[k=0:D] r^(n+k)/(1-r)^(k+1) * Delta^k P(n) It can be verified that r^n * P(n) = f(n,r) - f(n+1,r) so that we have a tool for closed form of the sums ------------------------------------------------ P(0) + r*P(1) + r^2*P(2) + ... + r^(n-1)*P(n-1) = f(0,r) - f(n,r) ------------------------------------------------ Motivation? For r less than 1 in magnitude, we can get a closed form for sum[m=n : infinity] r^m * P(m), and the formal result makes sense for all r except 1. (Yes, r can be complex.) Cheers, ZVK(Slavek).
From: Jon Slaughter on 3 Dec 2009 22:40
Tim Little wrote: > On 2009-12-03, Jon Slaughter <Jon_Slaughter(a)Hotmail.com> wrote: >> 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. > > And 1/9 is not, because no matter how many 1s you put in 0.1111..., > you'll never get exactly 1/9? > > Or if you don't like that example, how about sqrt(2)? Certainly the > Pythagoreans thought there was a huge difference between it and 1/9. Do you realize that at some point in history sqrt(2) was not computable? they had no idea what it was... remember it was called "irrational". Once it became possible to understand what it meant and that the it expressed a rather trivial property of numbers then it was considered elementary. Hence the reason why we have the distinction between "closed form" rather than just finitely computable. We went from elementary things to more complex things. What is elementary today may not be elementary tomorrow. But at some point a line has to be drawn else everything can be considered elementary. el�e�men�ta�ry /??l?'m?nt?ri, -tri/ Show Spelled Pronunciation [el-uh-men-tuh-ree, -tree] Show IPA Use elementary in a Sentence See web results for elementary See images of elementary �adjective 1.pertaining to or dealing with elements, rudiments, or first principles: an elementary grammar. 3.of the nature of an ultimate constituent; simple or uncompounded. hence sqrt(2) was not elementary. In fact one might consider that the only elementary things is the counting numbers. Of course this is far to limiting. exp(x) become elementary because of it's properties and it seems to be something of first principles. > >> exp(x) is a closed form representation in x. > > Yes. > > >> sum(x^k/k!,k=0..oo) is a closed form representation in x but not k. > > The symbol k is not a variable of that expression; it makes no sense > to evaluate the expression for different values of k. So it makes no > sense to even ask whether it is a closed-form representation in k. It > is not a closed form in x either, as the number of terms is infinite > for all x. K is most definitely a variable of the expression. It is required just as much as x. It is not a mathematical variable but is required to express the idea that the expression has. Similary .. is an symbol with mathematical meaning and is necessary to express an mathematical idea. The definition I used(I stated somewhere) was that that the variable needs to produce a finite number of terms. Since the sum is actually a limit of finite terms and x does not increase or decrease the number then it is of closed-form in x. that is exp(x) = lim n->oo sum(x^k/k!, k=1..n) Now I do see your point and you may be potentially correct depending on some precise definition of closed form. > >> 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. > > If some function is well-known enough to be worth the programming > effort to build into a computer algebra system in worldwide use, I'd > say it's at least reasonable to accept it as a closed form. Maybe... but you assume that it too actual work to "build into". I can easily build such functions in maple(and I'm sure in mathematica), distribute them and pay people to use them. Would you then say they are elementary. Basically you are saying the "elementary" is simply done by a vote. This is completely ridiculous. elementary has to do with our intellectual understanding of it. It is "elementary" because it is simple in some way. Elementary physics is simple and the lowest form of physics. It is something that is more than just wide spread use but something that is "common knowledge". It is not common knowledge simply because it is wide spread but because it is elementary. For example, It is common knowledge that Pi = 3.1415 but just because it is common knowledge is not the reason why it is true. Pi = 3.1415 was still true even when virtually no human understood it. (The symbol here is unimportant) > >> But does there not come a point when everything is called >> elementary? > > No, because there are infinitely many functions, and at any point only > finitely many can be considered elementary. > So, exp(2x) is elementary? What about exp(kx)? Does exp(kx) represent an entire infinite family of elementary functions or is itself just one elementary function? > >> Surely we can agree that exp(x) is much more elementary than >> Lerchphi? > > Yes, I can accept that. The exponential function is known to pretty > much everyone who passed high school mathematics. > >> 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). > > I think that does not work well. If sin(x) is elementary, then cos(x) > would be necessarily not elementary. Likewise for exp(x). In this case sin x and cos x are both equally elementary. There is no choice of one over the other and hence we just use both. They, in some sense, are from the same "equivalence class". What we need are some precise definitions to work on... That is the big problem with trying to argue about something that isn't well defined... > >> 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. > > It doesn't even appear to make syntactic sense. What are the symbols > over which you are summing, and what are the parameters of the > function? Is "e" Euler's constant, or a (possibly integer) fifth > parameter? > Do I have to spell everything out exactly? a,b,c,d,e,f,x,y,z,m,... are just variables. All I did was take the common summands of many of the common summation expression for what you guys consider as elementary functions(exp, zeta, etc...) and put in variables to be able to expess them. I'll explain why below. >> 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? > > I have no idea what properties that function would have or how it > would be symbolically related to any other functions for various > parameter values. Why would it be surely much more useful? As far as > I can tell, I have never encountered an expression in my mathematical > work that would be simplified by the use of that function. > > Unlike LerchPhi. sum(k^(an-d)*x^(bk)/(ck)!*Cr(m, e*k)*B_(f*k)(y)*exp(z*k),k=q..N) let a = 1, b = 0, c = 0, d = 0, m = 0, e = 0, f = 0, y = 0, z = 0, q = 0; This gives sum(k^n, k = 0..N) b = 1, c = 1, N = oo, rest = 0 exp(x) = sum(x^k/k!) d = d, q = 1, N = oo, rest 0 Zeta(d) = sum(k^(-d)) We can get several other well known functions, or some modified form of them, by simply choosing an a propriate subspace in the parameter space(which is simply the span of all the variables). I can easily add any function that is expressible as a single series(I can increase the number of sums to get more complex functions). All I am basically doing is unioning the symbolic expressions of the summands with a variable controlling the ability to "remove" it from the summand(since it is a product this means the variable has to produce a result of 1). Hence any such function is a generalization regardless of what it does over most of the parameter space. The fact is that at certain subspaces it represents a well known and useful function. Hence it is more useful since it is a generalization. It is not more elementary though. Lets simplify this a bit Surely you agree that the function f(x, s; a, b, c, d, q, N) = sum(x^(a*k)/(b*k + c)!*(k+d)^s,k=q..N) Is more "useful" than sum(x^k/k!) and sum(1/k^s) alone? i.e., exp(x) and zeta(s)? Why is it more useful? Because it is a generalization f(x, 0; 1, 1, 0, d, 0, oo) = exp(x) f(0, s; 0, 0, 0, 0, 1, oo) = zeta(s) Hence this new function contains two very important functions as special cases. It may contain several other special functions. For example, Lerchphi may be contained in there somewhere. That is, f may take on the same values as lerchphi for some subspace of parameters or can easily be transformed into such by simple means(such as a simple "elementary" transformation") e.g., It may be that LerchPhi(z,s,a) = f(x, sqrt(s); a, a, sqrt(a), cos(a*s), a, oo) So, an "elementary" function is a function that expresses something new in an atomic way. Suppose we have a "function of everything". It expresses all our functions. It is surely not elementary. But if we were able to partition parameter space into disjoint subspaces in a nice way then each function on the subspace might be called elementary, if say, it decomposed the function of everything into atomic units. I'm not saying this makes complete sense or is well defined but it is, in some sense how I think of elementary functions. There may be more than one way to parition the subspace and/or no such "function of everything". The point is that some functions seem more elementary than others and the goal is to have some small subset that represents everything and each elementary function is... well... elementary. This is exactly what mathematics does. We decomes complex things into easier things. We have the set of functions and decompose it into a set of elementary functions and non-elementary functions. If we have a "basis" of elementary functions then thats all we need to be able to write/compute/understand all the non-elementary ones. Again, I'm not saying it's well-defined or even completely thought out. It's not a theory but just my observations and thoughts on the subject. |