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

        riddles >> easy >> Identical limits
        
(Message started by: JocK on Jan 27th, 2005, 9:24am)
Title: Identical limits
Post by JocK on Jan 27th, 2005, 9:24am


a0 [in] [bbr], b0 [in] [bbr], n [in] [bbn]0

an+1 = (an + 1)1/3

bn+1 = (bn4 + 1)1/5

prove that a[infty] = b[infty]
Title: Re: Identical limits
Post by Icarus on Jan 27th, 2005, 3:29pm
You sure you won't let us take a0 and b0 from [bbc] instead? ;)
Title: Re: Identical limits
Post by JocK on Jan 31st, 2005, 2:21pm
No takers..? Perhaps I should change the problem somewhat:


Why would x3 - x - 1 = 0  and  x5 - x4 - 1 = 0  share the same positive root?



Title: Re: Identical limits
Post by towr on Jan 31st, 2005, 2:53pm
Yeah, I can get that far, and the graph certainly suggest they share the same root. But I haven't a clue how to prove it.

[e] How about something like
::[hide]x^3 -x - 1 = 0
x^3 = x + 1

x^5 - x^4 -1 = 0  { repeatedly replace x^3 by x + 1 }
x^2(x + 1) - x(x + 1) - 1 = 0
x^3 - x - 1 = 0
x + 1 - x - 1 = 0
true

So any x for which x^3 = x + 1 must be a solution for x^5 - x^4 -1 = 0  ?!?
[/hide]::[/e]
Title: Re: Identical limits
Post by JocK on Jan 31st, 2005, 3:57pm
OK... that's the easy way.  ;)

Now the more elegant way: someone dare to cast this observation into graphical form?
Title: Re: Identical limits
Post by Aryabhatta on Jan 31st, 2005, 3:59pm
I think Icarus already knew the solution and was waiting...

Anyway it is easy to prove that the x^3 - x -1 and x^5 - x^4 - 1 each have only 1 real root.

From there it is easy to prove that the roots must be the same:

x^3 = x +1
implies (multiplying by x^2)
x^5 = x^3 + x^2 = x^2 + x + 1  
and also
x^4 = x^2 + x (multiply by x)

Thus x^5 = x^4 + 1

Only thing left to prove is that both sequences converge.
Title: Re: Identical limits
Post by Icarus on Jan 31st, 2005, 4:23pm

on 01/31/05 at 15:59:23, Aryabhatta wrote:
I think Icarus already knew the solution and was waiting...


I did. Polynomial division reveals that x5 - x4 - 1 = (x3 - x - 1)(x2 - x + 1).

The quadratic is easily seen to have no real roots. Showing that the cubic has only one real root is a little harder (unless you remember that signs theorem that I never do). Thus the quintic and cubic share a single real root. And if an and bn converge, they have to converge to it.
Title: Re: Identical limits
Post by Barukh on Jan 31st, 2005, 11:18pm

on 01/31/05 at 14:21:43, JocK wrote:

Why would x3 - x - 1 = 0  and  x5 - x4 - 1 = 0  share the same positive root?

Why positive?


on 01/31/05 at 16:23:50, Icarus wrote:
Polynomial division reveals that x5 - x4 - 1 = (x3 - x - 1)(x2 - x + 1).

…Showing that the cubic has only one real root is a little harder (unless you remember that signs theorem that I never do).

The cubic x3 - x – 1 has the same extremum points as x3 – x. The latter has 3 real roots -1, 0, 1, so both cubics have local maximum in the interval I1 = (-1, 0), and local minimum in the interval I2 = (0, 1). Because x3 – x < 1 for x [in] I1, it follows x3 - x – 1 < 0 for x < 1. Therefore, it has only one real root.
Title: Re: Identical limits
Post by JocK on Feb 1st, 2005, 1:34pm

on 01/31/05 at 23:18:26, Barukh wrote:
Why positive?


Well.... the geometrical construction I'm interested in demonstrates in one go that both polynomials share a root that has to be positive.


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