Warning anger Ahead

  • Thread starter steven187
  • Start date
176
0
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]
Prove
[tex]\lim_{n\rightarrow\infty} F(n)=0[/tex]
 

Zurtex

Science Advisor
Homework Helper
1,120
1
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).
 

saltydog

Science Advisor
Homework Helper
1,582
2
Zurtex, when I plug it into Mathematica, it goes to zero quickly: by n=5 it's 10^-6 already.
 
176
0
[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
 

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

Zurtex

Science Advisor
Homework Helper
1,120
1
saltydog said:
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 :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:

saltydog

Science Advisor
Homework Helper
1,582
2
Zurtex said:
And yet at n=27 it's about 0.0148786, you must remember the frivolous theorem of arithmetic :tongue:
Thanks. I'll try and remember this. I would have concluded, incorrectly, that it was monotonic. :smile:
 
176
0
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:
 
1,570
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.
 
1,570
1
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).

phoenixthoth said:
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
By stirling's approximation, we have:

[tex]
\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}}
[/tex]

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:

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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.
 
1,570
1
Hurkyl said:
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?
 
Last edited:

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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.
 
1,570
1
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.

Hmm...
 
176
0
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:

steven
 
1,570
1
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. :(
 
1,570
1
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...
 
1,570
1
I've taken the postive and negative parts of [tex]\sum_{k=1}^{n-1}\left( 1-\frac{n}{k}\right) ^{k}[/tex] and separated them. The sum looks like this:
[tex]-\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}[/tex]. 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 [tex]\sum_{k=1}^{n-1}\left( 1-\frac{n}{k}\right) ^{k}<d(n)[/tex]
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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:

[tex]
S = \left| \sum_{k=p}^{n-1} \frac{(k-n)^k e^{-k}}{k!} \right|
< \frac{(n - p)^k e^{-p}}{p!}
[/tex]

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

[tex]
e^n S < \frac{1}{\sqrt{2 \pi p}} p^{-p} e^{p - 1/(12p + 1)} (n-p)^p e^{n-p}
[/tex]
[tex]
e^n S < \frac{1}{\sqrt{2 \pi p}} e^n \left( \frac{n-p}{p} \right)^p
[/tex]

So, if we fix [itex]p = a n[/itex], we have:

[tex]
e^n S < \frac{1}{\sqrt{2 \pi a n}} \left( e \left( \frac{1-a}{a} \right)^a \right)^n
[/tex]

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!!)
 
Last edited:
1,570
1
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, [tex]G\left( n\right) =\sum_{k=0}^{n-1}\frac{e^{-k}\left( k-n\right) ^{k}}{k!}[/tex]. Then we can break this up where p=Floor[n/2] or Floor[n/2]+1:

[tex]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!}[/tex].

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

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

Now if we take the limit, we get
[tex]\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) [/tex].

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

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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
I'm hoping we can split the summation up into 3 or 4 pieces, and bound each piece individually.
 
1,570
1
I was just numerically approximating the last limit which is supposed to go to zero.

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

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???
 

Related Threads for: Warning anger Ahead

  • Last Post
Replies
19
Views
3K

Hot Threads

Top