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

Challenge X: French fish

  1. Aug 18, 2013 #1

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Find the following limit:

    [tex]\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!}[/tex]
     
  2. jcsd
  3. Aug 19, 2013 #2
    I have the vaguest feeling that the limit is 1. I'm too tired to prove it right now. I'll get back to it soon. :tongue:

    Edit: Probably not. Looking at it now, as shown below, it is an upper bound. Taking the expansion out a couple terms, it looks like it's less than 0.6.

    Why is this called french fish? Is this hinting at using something by Poisson?
     
    Last edited: Aug 19, 2013
  4. Aug 19, 2013 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Well, 1 is an upper limit:
    $$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} \leq \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^\infty \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} 1 = 1$$

    It is interesting that
    $$\lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^n \frac{n^k}{k!} = \lim_{n\rightarrow +\infty} e^{-n} \sum_{k=0}^{n-1} \frac{n^k}{k!}$$ but I am not sure how to convert this to a lower limit on the limit.

    Edit: Okay, that approach does not work. And the limit is not 1. I guess 1/2.

    The question can be re-phrased as "in a Poisson distribution with expectation value n, what is the probability to get at most the expectation value?" - and then the limit of n->infinity. As the Poisson distribution approaches a Gaussian distribution, I would expect 1/2 as limit.
     
    Last edited: Aug 19, 2013
  5. Aug 19, 2013 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Right. The limit is indeed 1/2. And an application of the central limit theorem gives the answer. Well done!
     
  6. Aug 19, 2013 #5
    I worked out that the limit is less than or equal to 0.5:

    Reversing it and using the Taylor series for e:
    [tex]\frac{e^{n}}{ \sum_{k=0}^n \frac{n^k}{k!}}=1+\frac{\sum_{k=n+1}^\infty \frac{n^k}{k!}}{ \sum_{k=0}^n \frac{n^k}{k!}}[/tex]
    Introducing [itex]x=\frac{n^n}{n!}[/itex]
    [tex]\frac{\sum_{k=n+1}^\infty \frac{n^k}{k!}}{ \sum_{k=0}^n \frac{n^k}{k!}}=\frac{x \frac{n}{n+1}+x \frac{n}{n+1} \frac{n}{n+2}+...}{x+x+x\frac{n-1}{n}+x\frac{n-1}{n}\frac{n-2}{n}+...}=\frac{\frac{n}{n+1}+\frac{n}{n+1} \frac{n}{n+2}+...}{2+\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}[/tex]
    The number of terms in the numerator is infinity, the denominator goes until the terms reach zero. For very large n we have a lot of terms close to 1, so we can neglect the 2. Since [itex]\frac{n}{n+a} > \frac{n-a}{n}[/itex] and replacing some of the terms in the numerator like that to get a 1 the result is:
    [tex]\frac{\frac{n}{n+1}+\frac{n}{n+1} \frac{n}{n+2}+...}{\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}>1+\frac{\sum_{k=1}^\infty \frac{(n)!n^k}{(2n+k)!}}{\frac{n-1}{n}+\frac{n-1}{n}\frac{n-2}{n}+...}[/tex]
    For large n the numerator of the second term goes to zero.

    When I discarded the 2, maybe the denominator and numerator are quite equal, their difference is small and the 2 makes the denominator actually bigger. But in the limit it should be negligible, so the limit of the reciprocal is 2 or larger and the limit of the original expression is 0.5 or smaller.
     
  7. Aug 19, 2013 #6

    lurflurf

    User Avatar
    Homework Helper

    You really like Obfuscation.
    since
    $$e^{-n} \sum_{k=0}^n \frac{n^k}{k!}=\left( 1+ \gamma(n+1,n)/\Gamma(n+1,n) \right)^{-1}$$
    Why not just ask
    $$\lim_{n\rightarrow \infty} \gamma(n+1,n)/\Gamma(n+1,n)=\lim_{n\rightarrow \infty} \int_0^n t^n e^{-t} \mathrm{d}t {\huge/} \int_n^\infty t^n e^{-t} \mathrm{d}t=1$$
     
  8. Aug 19, 2013 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    You don't seem to grasp the concept of a challenge :tongue:
     
  9. Aug 20, 2013 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Well done by mfb for finding the solution. The (partial) solution by chingel is also very nice!

    And a special thanks to lurflurf for showing another neat interpretation of this problem!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge X: French fish
  1. French translation (Replies: 9)

  2. Master's Challenge (Replies: 15)

  3. A Euclidean Challenge (Replies: 10)

Loading...