Warning anger Ahead

1. Jun 11, 2005

steven187

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 $$\forall n\in\aleph$$

$$F(n)= 2n+\frac{2}{3}-e^n\sum_{k=0}^{n-1}\frac{(k-n)^k e^{-k}}{k!}$$
Prove
$$\lim_{n\rightarrow\infty} F(n)=0$$

2. Jun 12, 2005

Zurtex

First of all do you mean:

$$\forall n \in \mathbb{N}$$?

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).

3. Jun 12, 2005

saltydog

Zurtex, when I plug it into Mathematica, it goes to zero quickly: by n=5 it's 10^-6 already.

4. Jun 12, 2005

steven187

$$\forall n \in \mathbb{N}$$ 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 $$e^{n}$$ 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
$$F_{n}(x)= 2n+\frac{2}{3}-\sum_{k=0}^{n-1}\frac{d^k}{dx^k}[\frac{e^{(k-n)x}}{k!}]$$ 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

5. Jun 13, 2005

rachmaninoff

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 $$lim_{n->\infty}\sum_{k=0}^{\infty}\frac{(k-n)^k e^{-k}}{k!}$$ (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 $$\Sigma$$ 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
$$lim_{n->\infty}\sum_{k=0}^{n}\left( \frac{(k-n)^k e^{n-k}}{k!}-2k \right) =\frac{2}{3}$$
I know at the very least it would be sufficient (maybe necessary?) if
$$lim_{n->\infty}\sum_{k=0}^{\infty}\left( \frac{(k-n)^k e^{n-k}}{k!}-2k \right) =\frac{2}{3}$$

sorry if this is confusing - I'm typing quickly and it's 3:17 in the morning...

6. Jun 13, 2005

steven187

hello
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

steven

7. Jun 13, 2005

Zurtex

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
8. Jun 13, 2005

saltydog

Thanks. I'll try and remember this. I would have concluded, incorrectly, that it was monotonic.

9. Jun 14, 2005

steven187

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:

10. Jun 18, 2005

phoenixthoth

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.

11. Jun 18, 2005

phoenixthoth

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).

12. Jun 18, 2005

Hurkyl

Staff Emeritus
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 $e^{-n}$, 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
13. Jun 18, 2005

Hurkyl

Staff Emeritus
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.

14. Jun 18, 2005

phoenixthoth

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
15. Jun 18, 2005

Hurkyl

Staff Emeritus
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.

16. Jun 18, 2005

Hurkyl

Staff Emeritus
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.

17. Jun 19, 2005

phoenixthoth

So F(n) can be re-written as, where lambda[k] is between 1/(12k+1) and 1/(12k):
$$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}}$$.

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

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

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

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

Hmm...

18. Jun 19, 2005

steven187

hello all

hello phoenixthoth, well your right i dont think induction is the best path to take, now in terms of your last inequality
$$e^{-n}\left( 2n+2/3-e^{-n}\right) <G\left( n\right) <e^{-n}\left( 2n+2/3+e^{-n}\right)$$
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

steven

19. Jun 19, 2005

phoenixthoth

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. :(

20. Jun 19, 2005

phoenixthoth

I made a boo-boo.

G(n) equals
$$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}$$.

At least, I think so...

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook