wu :: forums - Print Page


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

        riddles >> easy >> Monotonic Sequence to calculate roots
        
(Message started by: Aryabhatta on Nov 30^th, 2004, 11:26am)

Title: Monotonic Sequence to calculate roots
Post by Aryabhatta on Nov 30^th, 2004, 11:26am

The sequence {a_n} is recursively defined as follows:

(k+1)a_n+1 = (ka_n+ M/a_n^k)

where k is a fixed positive integer, M is a fixed real number > 0 and a₁ > 0.

This sequence might look weird, but it is actually a way to calculate the (k+1)^th root of M. Putting k = 1 gives us the oft used method of calculating square roots.

The problem:
Show that a_n+1 [le] a_n forall n > 1.

Try not to use calculus (it is in the easy forum :D).

Title: Re: Monotonic Sequence to calculate roots
Post by Barukh on Dec 1^st, 2004, 9:48am

[smiley=blacksquare.gif][hide]
Let m = (k+1)-th root of M.

1. a_n [ge] m for every n > 1. Indeed, use the AM/GM inequality on k+1 numbers a_n, …, a_n (k times), M/a_n^k:
(k+1)a_n+1 [ge] (k+1)^k+1[sqrt]M = (k+1)m.
2. If a_n [ge] m, then a_n+1 [le] a_n, since
M/a_n^k = a_n(m/a_n)^k+1 [le] a_n.
[/hide][smiley=blacksquare.gif]

Nice problem, Aryabhatta!

Title: Re: Monotonic Sequence to calculate roots
Post by Aryabhatta on Dec 1^st, 2004, 11:05am

Well done Barukh! I had exactly that solution in mind.

In fact with what you have shown, we can easily show that the sequence converges to the (k+1)^th root of M. (It follows because: [hide]The sequence is monotonically decreasing and bounded below (as shown in the proof), so it converges. That the limit is m follows easily [/hide]).

Here is another one in similar vein.

Show that the sequence {n^1/n} converges to 1.

Title: Re: Monotonic Sequence to calculate roots
Post by TenaliRaman on Dec 1^st, 2004, 9:09pm

Highly non-rigorous proof
::[hide]
let L = lim(n->inf) n^1/n
taking log on both sides,
log L = lim(n->inf) (1/n)log(n)
n grows faster than log n
therefore the RHS is zero
L = 1
(err we were not supposed to use calculus here too?)
[/hide]::

Title: Re: Monotonic Sequence to calculate roots
Post by Aryabhatta on Dec 1^st, 2004, 10:32pm

Tenali, Your argument works because if f is continuous and a_n converges to L then f(a_n) converges to f(L).

You can take f(x) = e^x and a_n = ln(n^1/n) = ln(n)/n which tends to 0 as you noted.

But yes, I was looking for a more elementary argument, which is a lot similar to Barukh's solution to the original puzzle of this thread.

Title: Re: Monotonic Sequence to calculate roots
Post by Aryabhatta on Dec 10^th, 2004, 4:47pm

This is the solution I had in mind for the n^1/n -> 1 problem.

Assume n > 3.

Consider the n numbers [sqrt]n,[sqrt]n, 1, 1, 1 ...,1

Applying AM [ge] GM to these we see that

(2[sqrt]n+n-2)/n [ge] n^1/n
Combining with n^1/n [ge] 1 we see that

1 + 2/[sqrt]n - 2/n [ge] n^1/n [ge] 1

Thus n^1/n -> 1 as n -> oo, by sandwich principle.

Title: Re: Monotonic Sequence to calculate roots
Post by Icarus on Dec 11^th, 2004, 7:53am

tsk, tsk, tsk... The Sandwich Principle is also calculus. (But then, how exactly can you show what the limit of a sequence is without calculus? ;))

Title: Re: Monotonic Sequence to calculate roots
Post by Aryabhatta on Dec 11^th, 2004, 5:11pm

on 12/11/04 at 07:53:22, Icarus wrote:

tsk, tsk, tsk... The Sandwich Principle is also calculus. (But then, how exactly can you show what the limit of a sequence is without calculus? ;))

;D

The no calculus restriction was for the original puzzle. As for the n^1/n one I was trying to avoid the canon. Also why do you think finding limits implies usage of calculus? I have seen a lot of people argue that 0.999....< 1 without knowing an ounce of calculus... All those people cannot be wrong now, can they? ::)

Title: Re: Monotonic Sequence to calculate roots
Post by Icarus on Dec 11^th, 2004, 6:50pm

Because limits are a part of calculus. Calculus is the mathematics of limiting processes.

Title: Re: Monotonic Sequence to calculate roots
Post by Aryabhatta on Dec 12^th, 2004, 12:57am

on 12/11/04 at 18:50:46, Icarus wrote:

Because limits are a part of calculus.

Yes of course. Maybe I should have used a different smiley. :-/ ;D

Title: Re: Monotonic Sequence to calculate roots
Post by Icarus on Dec 12^th, 2004, 10:37am

Hey, I've been fighting a really nasty cold. You can't expect me to catch every bit of sarcasm in this condition! :D