Prove F(n)→0 as n→∞ Warning: Danger Ahead?

[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

 

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

 

[saltydog]

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

 

[steven187]

\forall n \in \mathbb{N} yep that's 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 realized 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 I am going anywhere here coz this is where i get lost i don't 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

 

[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. dependence 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...

 

[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 I am 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

 

[Zurtex]

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

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

I think I might have typed it into 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.

 

[saltydog]

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

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

 

[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

 

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

 

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

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.

 

[Hurkyl]

By stirling's approximation, we have:

<br /> \frac{1}{\sqrt{2 \pi k}}\left(1 - \frac{n}{k}\right)^k e^{-\frac{1}{12k}}<br /> &lt;<br /> \frac{(k-n)^k e^{-k}}{k!}<br /> &lt;<br /> \frac{1}{\sqrt{2 \pi k}}\left(1 - \frac{n}{k}\right)^k e^{-\frac{1}{12k+1}}<br />

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.

 

[Hurkyl]

Replace n with n+1 to get:

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.

 

[phoenixthoth]

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.

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?

 

[Hurkyl]

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.

 

[Hurkyl]

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.

 

[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| &lt;\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) &lt;G\left( n\right) &lt;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...

 

[steven187]

hello all

hello phoenixthoth, well your right i don't think induction is the best path to take, now in terms of your last inequality
e^{-n}\left( 2n+2/3-e^{-n}\right) &lt;G\left( n\right) &lt;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 don't know how fast G(n) goes to zero), I am 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

 

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

 

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

 

[phoenixthoth]

I've taken the postive and negative parts of \sum_{k=1}^{n-1}\left( 1-\frac{n}{k}\right) ^{k} and separated them. The sum looks like this:
-\sum_{k=1}^{\frac{n-1}{2}}\left( \frac{n}{2k-1}-1\right) ^{2k-1}+\sum_{k=1}^{\frac{n-1}{2}}\left( \frac{n}{2k}-1\right) ^{2k}. This is for odd n; I believe there would be a similar formula for even n.

My main goal now is to find a d(n) such that \sum_{k=1}^{n-1}\left( 1-\frac{n}{k}\right) ^{k}&lt;d(n)
and d(n) is as small as possible.

Then hopefully I will have an upper bound on G(n).

I'd like to say that these sums now that they have positive terms are bounded by some evaluatable integral. However, the terms are not monotonic even when sign is removed. Ugh!

 

[Hurkyl]

Progress

I can bound away a good portion of the sequence.

The terms of the summation are decreasing when k > n/2. (check?) So, we can do the usual stuff with alternating series.

We have:

<br /> S = \left| \sum_{k=p}^{n-1} \frac{(k-n)^k e^{-k}}{k!} \right|<br /> &lt; \frac{(n - p)^k e^{-p}}{p!}<br />

Now, if we mix in the e^n in front and apply stirling's formula...

<br /> e^n S &lt; \frac{1}{\sqrt{2 \pi p}} p^{-p} e^{p - 1/(12p + 1)} (n-p)^p e^{n-p}<br />
<br /> e^n S &lt; \frac{1}{\sqrt{2 \pi p}} e^n \left( \frac{n-p}{p} \right)^p<br />

So, if we fix p = a n, we have:

<br /> e^n S &lt; \frac{1}{\sqrt{2 \pi a n}} \left( e \left( \frac{1-a}{a} \right)^a \right)^n<br />

So, all we need to do is to fix a large enough so the term inside the parentheses is less than 1. Then, as n goes off to infinity, we have that the tail portion (from an to n-1) of the summation goes to zero.


(I wouldn't mind having my work checked!)

 

[phoenixthoth]

Nice job. I think any a between 1/2 and 1 would work. a=3/4.

If I understand this approach, it's basically basic calculus. I'm worried about how there is an n in the summand and the AST never speaks of this. I should just think about it and decide but I'm worried about what this would do for us at this point, if true (and I think/hope it is).

At some point, I think we have to prove that the absolute value of the summand is decreasing when k>n/2. There induction may be helpful.

As I recall, G\left( n\right) =\sum_{k=0}^{n-1}\frac{e^{-k}\left( k-n\right) ^{k}}{k!}. Then we can break this up where p=Floor[n/2] or Floor[n/2]+1:

G\left( n\right) =\sum_{k=0}^{p-1}\frac{e^{-k}\left( k-n\right) ^{k}}{k!}+\sum_{k=p}^{n-1}\frac{e^{-k}\left( k-n\right) ^{k}}{k!}.

Then S(n) is defined above and T(n) is what's left: G(n) - S(n):
T\left( n\right) =\sum_{k=0}^{p-1}\frac{e^{-k}\left( k-n\right) ^{k}}{k!}.

We have:
F\left( n\right) =2n+2/3-e^{n}T\left( n\right) -e^{n}S\left( n\right).

Now if we take the limit, we get
\lim_{n\rightarrow \infty }F\left( n\right) =\lim_{n\rightarrow \infty }\left( 2n+2/3-e^{n}T\left( n\right) -e^{n}S\left( n\right) \right).

We know that:
\lim_{n\rightarrow \infty }e^{n}S\left( n\right) =0;
so now we hope that it can be shown that \lim_{n\rightarrow \infty }\left( 2n+2/3-e^{n}T\left( n\right) \right) =0.

Hmm... Wait a sec. This is like the same damn thing except that the upper limit is SMALLER than n-1. There's something fishy going on here.

 

[Hurkyl]

I'm hoping we can split the summation up into 3 or 4 pieces, and bound each piece individually.

 

[phoenixthoth]

I was just numerically approximating the last limit which is supposed to go to zero.

\lim_{n\rightarrow \infty }\left( 2n+2/3-e^{n}T\left( n\right) \right) =0

My 'puter is telling me that the limit is not zero (I plotted the thing that is supposed to go to zero and it was possible to do because I had Floor somewhere in the sum).

Hmm...

I don't want to try proving something that's false. So I'm not sure we should split the sum in two like that but on what basis do we split the sum?

 

[Hurkyl]

Well, a = 3/4 is too small:

e ((1 - a) / a)^a ~ 1.19, so my bound doesn't work there. Try a = 4/5?


That is sort of disappointing... I thought my bound covered more of the sum than that.

 

[phoenixthoth]

Well, a = 3/4 is too small:

e ((1 - a) / a)^a ~ 1.19, so my bound doesn't work there. Try a = 4/5?


That is sort of disappointing... I thought my bound covered more of the sum than that.

I see. I missed the e in front. 4/5 works as does 99/100. So the smaller of the two being the more elegant, we can use 4/5.


Well, well, well... Maybe that is why my limit didn't seem to go to zero, because I was going up to Floor[3/4n]. Let me see if this:
\lim_{n\rightarrow \infty }\left( 2n+2/3-e^{n}T\left( n\right) \right) =0
appears true when a=4/5...

Well it's better behaved but still doesn't go to zero...

Now that we've related T(n) in there, I'm wondering if I can return to the proof that |F(n)|<(1/e)^n which has good numerical evidence. Smaller numbers than 1/e work but it seems like e is the best choice. I'm wondering now if complete induction (cuz we have p=3n/4) will *somehow* be made to work.

 

[phoenixthoth]

This is really going to get me frustrated if it doesn't work.

Note that G(n)=G(Floor[4n/5])+S(n).

So by complete induction, G(Floor[4n/5]) is small and Hurkyl showed that S(n) is small so hopefully G(n) is also small.

Hmm...

 

[Hurkyl]

So your calculations show that the region between 3n/4 and 4n/5 is relevantly large. The sum, I'm sure, goes to zero as n goes to infinity, but not fast enough to kill the e^n factor. I wonder if that will give any useful hints?

 

[phoenixthoth]

Question:

In the first post you made where you bounded S(n)...

You have an inequality and on the right you have p's in 3 places. Should those p's be p+1? I'm not sure how much that'd help, if at all, anyway.

EDIT:

nevermind; I think it's right.

 

[phoenixthoth]

So your calculations show that the region between 3n/4 and 4n/5 is relevantly large. The sum, I'm sure, goes to zero as n goes to infinity, but not fast enough to kill the e^n factor. I wonder if that will give any useful hints?

Yes. T(n) definitely goes to zero.

I've also noticed that (2n+2/3)/(T(n)e^n)-->0 as n-->Infinity. Not sure if that helps or, better yet, how to prove it even if it is helpful. I have a feeling it MAY be helpful...


Hmm...

 

[phoenixthoth]

I got to find out just how smart I am today.

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=20848" thread describes the solution of the problem. I wasn't thinking in this direction at all and I wouldn't have used this method.

 

[steven187]

hello all

well I only get some of your approaches, I have given up upon mathematical induction and spliting up the sums a while ago, but see I went to pay an old friend a visit who is a mathematician, he looked at the question and said to me "try using complex numbers" that's when I walked of in confusement, so just recently I have been researching into complex analysis but I aint getting anywhere, does anybody understand how to find a limit of a series through complex numbers, it even sounds weird " but he sounded so certain", I would really love to know if there is, and it would be great if someone could provide us with some links on this,

thank you

steven

 

[phoenixthoth]

hello all

well I only get some of your approaches, I have given up upon mathematical induction and spliting up the sums a while ago, but see I went to pay an old friend a visit who is a mathematician, he looked at the question and said to me "try using complex numbers" that's when I walked of in confusement, so just recently I have been researching into complex analysis but I aint getting anywhere, does anybody understand how to find a limit of a series through complex numbers, it even sounds weird " but he sounded so certain", I would really love to know if there is, and it would be great if someone could provide us with some links on this,

thank you

steven

Check the link in the post above yours. Indeed, complex numbers/analysis was used.

 

[steven187]

hello all

hmmm I see, well to me it looks like they have turned it into a continuous function and some how used the inverse laplace transform to find out the pattern of such a distribution, but its funny I couldn't imagine this being related to statistical analysis, but yeah there aint that much complex numbers, my friend sounded like it can be completely solved through complex numbers, well anyway I am going to keep readin these complex analysis books that i have, I hope they will be of some help, il update you if i get anywhere

steven

 

[phoenixthoth]

This has been a cool problem, if damn frustrating.

I bought some small books on asymptotic analysis because this stuff is really interesting.

Thanks for posting it.

Cheers

 

[steven187]

hello all

in terms of this problem I have been looking at the laurent series, I have been playing around with it but I keep coming across dead ends, see I remember reading once that you can do a lot with the complex field especially to solve problems in the real number field, now to find the sum of a series, would using the laurent series be the best place to start for attempting this problem in the complex field? if not where is the best place to start to find the sum of a series in the complex field? any suggestions would be helpful

steven

 

[steven187]

hello all

well even after doing some research into complex analysis it didnt really give me much help, the only thing that i could find that could be possibly related to it is the laurent series but can't figure out how to apply it to this problem, so I decided to go and as a friend who is a lecturer in analysis, he had one look at this question and said it definitely has something to do with this theorem how sounded very certain

Cauchys Theorem
if f(z) is analytic and

\frac{f(z)}{z-z_{o}}

has a simple pole at z_{0}

with residue f(z_{o})

then the theorem says that if f(z) is analytic within C the value of f at some point z_{0}
within C is given by

f(z_{0})=\frac{1}{2\pi i} \oint_{C}\frac{f(z)}{z-z_{o}} dz

would anybody have any idea on how to apply this theorem to this Problem, I honestly can't see the link, any suggestions would be appreciated

steven