Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Warning anger Ahead

  1. Jun 11, 2005 #1
    Warning:Danger Ahead

    hello all

    over the last few days Iv been working on this question, but i am seriously left speachless, this will most likely be the hardest question I have ever attempted if anybody is up for a challenge be prepared... alright here we go
    we have [tex]\forall n\in\aleph[/tex]

    [tex] F(n)= 2n+\frac{2}{3}-e^n\sum_{k=0}^{n-1}\frac{(k-n)^k e^{-k}}{k!}[/tex]
    [tex]\lim_{n\rightarrow\infty} F(n)=0[/tex]
  2. jcsd
  3. Jun 12, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    First of all do you mean:

    [tex]\forall n \in \mathbb{N}[/tex]?

    What have you attempted so far? Also, I feel it worth mentioning that I plugged this in to Mathematica and it seems to think that the function tends to infinity (it was also able to simplify the function to something mainly in terms of the gamma function).
  4. Jun 12, 2005 #3


    User Avatar
    Science Advisor
    Homework Helper

    Zurtex, when I plug it into Mathematica, it goes to zero quickly: by n=5 it's 10^-6 already.
  5. Jun 12, 2005 #4
    [tex]\forall n \in \mathbb{N}[/tex] yep thats what it was suppose to be well in terms of what I have done was I tried to play around with it to try to get something I recognise well when i placed the [tex] e^{n}[/tex] after the sum and then i realised that the coefficient is the same as the power of e so I decided to turn it into a series of functions in which i would get
    [tex] F_{n}(x)= 2n+\frac{2}{3}-\sum_{k=0}^{n-1}\frac{d^k}{dx^k}[\frac{e^{(k-n)x}}{k!}][/tex] i really doubt im going anywhere here coz this is where i get lost i dont know how to turn that into something i recognise or some way of finding the limite function in which all i have to do is substitute x= -1, so the problem seems impossible but true
  6. Jun 13, 2005 #5
    I've put several hours into this, what I've tried so far (things that don't seem to work) is

    (1) treat the last term as [tex]lim_{n->\infty}\sum_{k=0}^{\infty}\frac{(k-n)^k e^{-k}}{k!}[/tex] (the limit is split, the limit in the sum is evaluated to infinity before the parameter 'n' is modified') and trying to simplify it to a closed form, for example by substituing the binomial expansion of the ^k power, and/or the exponential's power series, and rearranging stuff in the nested sums (doesn't work). I looked up a table of series expansions, it's nothing familiar (the e^k factor is unusual). And of course there it cannot be a Taylor series because of its exp. dependance on k, the parameter of summation.

    (2) move the 2n term into the sum, as a (-2k) term; this should force the sum to become Cauchy - which I'm trying to prove.

    (quick observation - the (n-1) in the [tex]\Sigma[/tex] is trivially the same as an 'n' because (n-n)=0).

    By (2), a perhaps slightly 'cleaner' form of the equation (or was the given form a hint of some sort?) is
    [tex]lim_{n->\infty}\sum_{k=0}^{n}\left( \frac{(k-n)^k e^{n-k}}{k!}-2k \right) =\frac{2}{3}[/tex]
    I know at the very least it would be sufficient (maybe necessary?) if
    [tex]lim_{n->\infty}\sum_{k=0}^{\infty}\left( \frac{(k-n)^k e^{n-k}}{k!}-2k \right) =\frac{2}{3}[/tex]

    sorry if this is confusing - I'm typing quickly and it's 3:17 in the morning...
  7. Jun 13, 2005 #6
    well exactly what i have typed in my first post is the question there are no hints, well I honestly have no idea im pretty lost my self with this question,I would look at it as if it were a miracle if there is a proof even thought it is true

  8. Jun 13, 2005 #7


    User Avatar
    Science Advisor
    Homework Helper

    And yet at n=27 it's about 0.0148786, you must remember the frivolous theorem of arithmetic :tongue:

    I think I might have typed it in to mathematica wrong anyway, sorry about that. After it grows again, it does appear to converge again to 0, after trying various values much greater than 25 it does appear to get less than 10^-(500) and not go above that again. However when I trying to get mathematica to take a limit, the Kernel crashes. I'll try and tackle with hand and paper later.
    Last edited: Jun 13, 2005
  9. Jun 13, 2005 #8


    User Avatar
    Science Advisor
    Homework Helper

    Thanks. I'll try and remember this. I would have concluded, incorrectly, that it was monotonic. :smile:
  10. Jun 14, 2005 #9
    hello all
    does anybody have any ideas on where to start with this question at least, now its really starting to give me head aches

    please help

    thanxs :grumpy:
  11. Jun 18, 2005 #10
    Thank you for posting this wonderfully frustrating problem!

    Here's what I've tried:
    Trying to convert the limit of the sum part into an integral. If I could make the summands a function of k/n, then I'd be ok but I can't see how to do that.

    Pretending that F(n) is the nth coefficient of a series. Proving the series converges would show that F(n) goes to 0. I haven't beaten this avenue to death yet; I haven't tried all viable convergence tests.

    Seeing if Mathematica can do it. It can't. Haven't tried other CAS's. One thing about Mathematica is that apparently the numbers are very sensitive and its approximations can be waaaay off; at first I thought the limit diverged. But when I was a little more careful, it does seem to converge. I start having accuracy issues around n=150 to 200.

    Trying to determine what that summand is the kth derivative of evaluated at 0. I think there's a post above about this.

    And I forget what else. Oh yeah, I also briefly searched for a similar problem.

    The current goose I'm following is this: proving, by induction, that for all n,
    |F(n)| <= (1/e)^n .

    This is true by mathematica for n up to 100. I started out with 1/2 instead of 1/e but then I tried 1/e and it still came out true for n up to 100. 1/e definitely seems like it will be better for this problem.
  12. Jun 18, 2005 #11
    I think I got it. Let me know if there are any errors.

    The method is to prove, by induction, that |F(n)| < (1/e)^n. This will then show that F(n) --> 0 by the squeeze theorem as e^(-n) --> 0.

    n=1. |F(1)|=e-8/3 ~ 0.052. (1/e)^1 ~ 0.368. Therefore, |F(1)| < (1/e)^1.

    Now assume that |F(n)| < (1/e)^n.

    We want to have |F(n+1)| < (1/e)^(n+1).

    Let G(n)=(2n+2/3-F(n))*e^(-n); i.e., the sum part of F(n).

    F(n)=2n + 2/3 - G(n) e^n.

    Then by induction,
    -(1/e)^n < 2n+2/3 - G(n) e^n < (1/e)^n.

    I will solve this for G(n) and then let n=n+1.

    Check my arithmetic but I think G(n) can be bounded by, from that last inequality, the following two extremes:
    e^(-n) (2n+2/3-e^(-n)) < G(n) < e^(-n) (2n+2/3+e^(-n)).

    Replace n with n+1 to get:
    e^(-n-1) (2n+2+2/3-e^(-n-1)) < G(n+1) < e^(-n-1) (2n+2+2/3+e^(-n-1)).

    (Sorry this isn't in tex!!!)

    Now I will build up to F(n+1) from this, knowing that
    F(n+1)=2n +2+ 2/3 - G(n+1) e^(n+1).

    Ok, first multiply all sides of the inequality by -e^(n+1) to get this:
    - (2n+2+2/3-e^(-n-1)) > -e^(n+1) G(n+1) > - (2n+2+2/3+e^(-n-1)); i.e.,

    - (2n+2+2/3+e^(-n-1)) < -e^(n+1) G(n+1) < - (2n+2+2/3-e^(-n-1)).

    Now, adding 2n+2+2/3 to this, I get
    -e^(-n-1)) < 2n+2+2/3-e^(n+1) G(n+1) < e^(-n-1); i.e.,
    -e^(-n-1)) < F(n+1) < e^(-n-1) ==> |F(n+1)|< (1/e)^(n+1).

  13. Jun 18, 2005 #12


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    By stirling's approximation, we have:

    \frac{1}{\sqrt{2 \pi k}}\left(1 - \frac{n}{k}\right)^k e^{-\frac{1}{12k}}
    \frac{(k-n)^k e^{-k}}{k!}
    \frac{1}{\sqrt{2 \pi k}}\left(1 - \frac{n}{k}\right)^k e^{-\frac{1}{12k+1}}

    That middle piece of the two sides looks awfully like [itex]e^{-n}[/itex], which approximately cancels out the factor outside the series.

    I haven't gotten any further, but it feels like this helps.
    Last edited: Jun 18, 2005
  14. Jun 18, 2005 #13


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This step looks wrong -- you haven't proven that inequality for all G yet. It sounds as if it's still in the proof idea stage.
  15. Jun 18, 2005 #14
    In that case, if we can prove that
    e^(-n) (2n+2/3 - e^(-n)) < G(n) < e^(-n) (2n+2/3 + e^(-n)) for all n, then we'd be done. Perhaps we can use your approximation formula?
    Last edited: Jun 18, 2005
  16. Jun 18, 2005 #15


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm becoming unhappy with my approximation -- it's only useful when k is large, and I don't think we can bound away the small k.

    I get the feeling we can split the sum into "small" and "large" k pieces, though, with the intermediate terms being negligable.
  17. Jun 18, 2005 #16


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    My bad, the large k don't really contribute all that much, since the k! dominates the term. So, it's mostly about the (alternating!) first so many terms.
  18. Jun 19, 2005 #17
    So F(n) can be re-written as, where lambda[k] is between 1/(12k+1) and 1/(12k):
    [tex]F\left( n\right) =2n+2/3-e^{n}\sum_{k=0}^{n-1}\frac{e^{-\lambda _{k}}(1-n/k)^{k}}{\sqrt{2\pi k}}[/tex].

    I believe that the way to go is to establish that
    [tex]\left| F\left( n\right) \right| <\left( 1/e\right) ^{n}[/tex] for all n>0.

    Now if we let G(n):=
    [tex]\sum_{k=0}^{n-1}\frac{e^{-\lambda _{k}}\left( 1-n/k\right) ^{k}}{\sqrt{2\pi k}}[/tex], then this can be re-written as showing that
    [tex]e^{-n}\left( 2n+2/3-e^{-n}\right) <G\left( n\right) <e^{-n}\left( 2n+2/3+e^{-n}\right) [/tex].

    If anyone can prove this last inequality, we're done.

    I'm not convinced that induction is the best way to do it.

  19. Jun 19, 2005 #18
    hello all

    hello phoenixthoth, well your right i dont think induction is the best path to take, now in terms of your last inequality
    [tex]e^{-n}\left( 2n+2/3-e^{-n}\right) <G\left( n\right) <e^{-n}\left( 2n+2/3+e^{-n}\right) [/tex]
    if we take the limit of all the terms in the inequality then the left side would approach 0 from the left and the right approaches 0 from the right, then by the squeeze theorem G(n)->0 as n-> infinity but if G(n) is the sum part of what we are trying to prove then you are also saying that f(n)->infinity since
    f(n)= 2n+2/3- G(n)e^n
    (i guess since i dont know how fast G(n) goes to zero), Im still working at it but aint going anywhere, anyway good luck with it and thanxs for helping, I hope we do get a solution coz I aint giving up :bugeye:

  20. Jun 19, 2005 #19
    This problem has caused me great enjoyment as well as agony.

    I ain't giving up, either.

    Yeah, the way G goes to zero is very special (in relation to multiplying it with e^n).

    Now if F(n)=2n+2/3- G(n)e^n and IF we could prove that
    (2n+2/3-1/e^n)/e^n < G(n) < (2n+2/3+1/e^n)/e^n, then we can manipulate the inequality first by multiplying it by e^n to get:
    2n+2/3-1/e^n < G(n)e^n < 2n+2/3+1/e^n
    then, negating everything
    -2n-2/3-1/e^n < -G(n)e^n < -2n-2/3+1/e^n.

    Now adding 2n+2/3 to each side yields:
    -1/e^n < F(n) < 1/e^n.

    In other words,

    (2n+2/3-1/e^n)/e^n < G(n) < (2n+2/3+1/e^n)/e^n implies
    -1/e^n < F(n) < 1/e^n.

    This would imply that F(n)-->0 as n-->Infinity.

    I've tested this last inequality up to n=100 and it's true so far so I believe that we can maybe prove that
    (2n+2/3-1/e^n)/e^n < G(n) < (2n+2/3+1/e^n)/e^n for all n.

    Hmm..:.. Not induction. Alllll right. :(
  21. Jun 19, 2005 #20
    I made a boo-boo.

    G(n) equals
    [tex]G\left( n\right) =1+\sum_{k=1}^{n-1}\frac{e^{-\lambda _{k}}}{\sqrt{2\pi k}}\left( 1-\frac{n}{k}\right) ^{k}[/tex].

    At least, I think so...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook