wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> x_(n+1) = sin(x_n)
        
(Message started by: Aryabhatta on Jul 27th, 2009, 4:22pm)
Title: x_(n+1) = sin(x_n)
Post by Aryabhatta on Jul 27th, 2009, 4:22pm
Consider the sequence

xn+1 = sin(xn)

x1 = 1.

Show that for any t, such that 0 < t < 1/2

the sequence

nt xn converges to 0 as n -> infinity.
Title: Re: x_(n+1) = sin(x_n)
Post by Aryabhatta on Jul 27th, 2009, 6:25pm
Also show that:

n0.5 xn converges to sqrt(3).

(i think this is so, i hope my working is right)
Title: Re: x_(n+1) = sin(x_n)
Post by Eigenray on Jul 27th, 2009, 8:17pm
Many moons ago, I showed the following on probability problem set.  You might find it interesting.

Background: In a [link=http://en.wikipedia.org/wiki/Branching_process]branching process[/link], we have a fixed probability distribution p, and in each generation, every individual independently has k offspring with probability p(k), k = 0,1,2,....  So if Xn is the number of individuals alive in generation n, then Xn+1 is the sum of Xn-many independent, identically distributed random variables.

Let's assume that X0 = 1, p(0) > 0, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif k p(k) = E(X1) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 1.

(a)  If http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif = 1 and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif2 < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif, then there exist constants 0 < c1 < c2 < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif such that
c1/n < P( Xn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0 ) < c2/n

(b) If http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif > 1, then there exist c,b > 0 such that P( extinction | Xn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0 ) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif ce-bn.


If we let
1 - ( sin http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{1-x} )2 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif pk xk,
then part (a) applies to show
c1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn < xn < c2/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn
for some c1,c2.
Title: Re: x_(n+1) = sin(x_n)
Post by Eigenray on Jul 27th, 2009, 8:54pm
I would guess that under the conditions of (a) above, we have generally that
n * P(Xn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0)  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif 2/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif''(1),
where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif p(k) xk.
If so this would imply n1/2 xn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3.
Title: Re: x_(n+1) = sin(x_n)
Post by Aryabhatta on Jul 28th, 2009, 10:28am
That is an interesting approach Eigenray. Do you have a proof of a) & b) written down somewhere?

The approach I had in mind:

I think we can show that

sqrt(3)/(sqrt(n) + 1) <= xn <= sqrt(3/n)

using

x - x3/6 <  sin(x) < x - x3/6 + x5/120
Title: Re: x_(n+1) = sin(x_n)
Post by Aryabhatta on Jul 28th, 2009, 2:09pm
I think I discovered a mistake in the 'proof' I had.

Back to the board.
Title: Re: x_(n+1) = sin(x_n)
Post by Eigenray on Jul 28th, 2009, 2:21pm
Background : If an = P( Xn = 0 ), then an+1 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(an) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/nearrow.gif a, where the probability of extinction, a, is the smallest positive root of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(a) = a.  We have a < 1 iff http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mu.gif = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif'(1) > 1.

It's a little awkward because it's phrased in terms of iterating http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif instead of what would be more natural, f(t) = 1 - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(1-t).

Suppose f : [0,1] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif [0,1] is sufficiently smooth, with f(0) = 0, f'(0) = 1, f''(x) < 0.  If xn+1 = f(xn), x0=1, then we should have n xn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif -2/f''(0).  Heuristically, we can think of f(x) ~ x(1-rx), and xn ~ 1/(r n).
Title: Re: x_(n+1) = sin(x_n)
Post by Aryabhatta on Jul 28th, 2009, 8:48pm
Actually, I reworked the whole thing and now it looks correct to me!

i.e. for all n > 0,

sqrt(3)/(sqrt(n) +1) < xn < sqrt(3/n)

Proved using (very tedious) induction on n, and the identities

x - x3/6 < sin x < x - x3 + x5/120.

The LHS is pretty straightforward, but the RHS yields a cubic

f(x) = 960x3 -520x2 + 111x - 9

which needs to be > 0 for x >= 1.

This has only one real root < 1, and so f(x) > 0 for x >= 1.

Perhaps we can simplify it.

I did find the result(inspite of the boring proof) to be interesting enough to post it here.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board