Author |
Topic: Monotonic Sequence to calculate roots (Read 536 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Monotonic Sequence to calculate roots
« on: Nov 30th, 2004, 11:26am » |
 Quote  Modify
|
The sequence {an} is recursively defined as follows:
(k+1)an+1 = (kan+ M/ank)
where k is a fixed positive integer, M is a fixed real number > 0 and a1 > 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 an+1 [le] an forall n > 1.
Try not to use calculus (it is in the easy forum  ).
|
| « Last Edit: Nov 30th, 2004, 12:07pm by Aryabhatta » |
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Monotonic Sequence to calculate roots
« Reply #1 on: Dec 1st, 2004, 9:48am » |
Quote Modify
|
[smiley=blacksquare.gif]
Let m = (k+1)-th root of M.
1. an [ge] m for every n > 1. Indeed, use the AM/GM inequality on k+1 numbers an, …, an (k times), M/ank:
(k+1)an+1 [ge] (k+1)k+1[sqrt]M = (k+1)m.
2. If an [ge] m, then an+1 [le] an, since
M/ank = an(m/an)k+1 [le] an.
[smiley=blacksquare.gif]
Nice problem, Aryabhatta!
|
| « Last Edit: Dec 1st, 2004, 9:51am by Barukh » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Monotonic Sequence to calculate roots
« Reply #2 on: Dec 1st, 2004, 11:05am » |
Quote Modify
|
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: The sequence is monotonically decreasing and bounded below (as shown in the proof), so it converges. That the limit is m follows easily ).
Here is another one in similar vein.
Show that the sequence {n1/n} converges to 1.
|
| « Last Edit: Dec 1st, 2004, 11:10am by Aryabhatta » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Monotonic Sequence to calculate roots
« Reply #3 on: Dec 1st, 2004, 9:09pm » |
Quote Modify
|
Highly non-rigorous proof
::
let L = lim(n->inf) n1/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?)
::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Monotonic Sequence to calculate roots
« Reply #4 on: Dec 1st, 2004, 10:32pm » |
Quote Modify
|
Tenali, Your argument works because if f is continuous and an converges to L then f(an) converges to f(L).
You can take f(x) = ex and an = ln(n1/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.
|
| « Last Edit: Dec 1st, 2004, 10:34pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Monotonic Sequence to calculate roots
« Reply #5 on: Dec 10th, 2004, 4:47pm » |
Quote Modify
|
This is the solution I had in mind for the n1/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] n1/n
Combining with n1/n [ge] 1 we see that
1 + 2/[sqrt]n - 2/n [ge] n1/n [ge] 1
Thus n1/n -> 1 as n -> oo, by sandwich principle.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Monotonic Sequence to calculate roots
« Reply #6 on: Dec 11th, 2004, 7:53am » |
Quote Modify
|
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?  )
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Monotonic Sequence to calculate roots
« Reply #7 on: Dec 11th, 2004, 5:11pm » |
Quote Modify
|
on Dec 11th, 2004, 7:53am, 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? ) |
|
The no calculus restriction was for the original puzzle. As for the n1/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? 
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Monotonic Sequence to calculate roots
« Reply #8 on: Dec 11th, 2004, 6:50pm » |
Quote Modify
|
Because limits are a part of calculus. Calculus is the mathematics of limiting processes.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Monotonic Sequence to calculate roots
« Reply #9 on: Dec 12th, 2004, 12:57am » |
Quote Modify
|
on Dec 11th, 2004, 6:50pm, Icarus wrote:| Because limits are a part of calculus. |
|
Yes of course. Maybe I should have used a different smiley. 
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Monotonic Sequence to calculate roots
« Reply #10 on: Dec 12th, 2004, 10:37am » |
Quote Modify
|
Hey, I've been fighting a really nasty cold. You can't expect me to catch every bit of sarcasm in this condition!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print