wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Positive root of x^n + x = 1
        
(Message started by: Aryabhatta on Oct 15^th, 2007, 3:40pm)

Title: Positive root of x^n + x = 1
Post by Aryabhatta on Oct 15^th, 2007, 3:40pm

This is from the book: "A problem Seminar" by Donald J Newman.

Show that the equation xⁿ + x = 1 has a unique positive real root r_n.

Find the limit of r_n as n -> oo.

How fast is the convergence?

Title: Re: Positive root of x^n + x = 1
Post by iyerkri on Oct 15^th, 2007, 8:02pm

[hideb] For n \geq 0,
g(x) = x^n + x -1 is strictly increasing for x \geq 0, with g(0) = -1 and g(1) = 1. Hence the first assertion follows.
[/hideb]

[hideb]
note 0 < r_n < 1. Let r_n = 1 - f(n).
suppose, f(n) does not go to zero as n goes to infinity. Then r_n^n goes to zero as n goes to infinity. but that means r_n goes to one, which means f(n) goes to zero, a contradiction.

Hence, f(n) goes to zero.

which means, r_n goes to 1 as n goes to infinity.

Also, r_n^n + r_n =1. thus, (1-f(n))^n = f(n).

for large enough n, (1-f(n))^n is of order exp(-nf(n))

Thus, order of f(n), say h(n), should satisfy the equation nh(n) + ln h(n) = 0.

I havent been able to find the exact form of h.
[/hideb]

~kris

Title: Re: Positive root of x^n + x = 1
Post by Aryabhatta on Oct 19^th, 2007, 1:52pm

Looks right.

According the Newman, 1 - r_n ~ [hide]logn/n[/hide]

Title: Re: Positive root of x^n + x = 1
Post by iyerkri on Oct 19^th, 2007, 4:50pm

That makes sense.

if we let [hide]g(n) = nh(n)[/hide], then we must have [hide] g(n) + log(g(n)) = log(n) [/hide], which implies [hide]log(n)/2 \leq g(n) \leq log(n)[/hide].

Sorry for not knowing how to use the math symbols in the forum. I follow latex.

~kris

Title: Re: Positive root of x^n + x = 1
Post by ThudanBlunder on Oct 22^nd, 2007, 7:17am

on 10/19/07 at 16:50:39, iyerkri wrote:

Sorry for not knowing how to use the math symbols in the forum. I follow latex.

~kris

Welcome to the forum, kris.

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1171644142