# Find the limit of a recursion formula

• Jun 1st 2009, 07:25 AM
pberardi
Find the limit of a recursion formula
Hello,
I am looking at this recursion formula in my Calculus book.
x_n+1 = 1/2(x_n + 2/x_n)
It goes on to say that we can find the limit of this sequence by doing this:
L = 1/2(L + 2/L) fine
but now it says that this can be rewritten as L^2 = 2 and that the limit is the square root of 2. How?

Could someone please explain the last two steps? Thank you so much.
• Jun 1st 2009, 07:46 AM
Soroban
Hello, pberardi!

It's only algebra . . .

Quote:

I am looking at this recursion formula in my Calculus book:
. . $\displaystyle x_{n+1} \:=\: \frac{1}{2}\left(x_n + \frac{2}{x_n}\right)$

It goes on to say that we can find the limit of this sequence by doing this:
. . $\displaystyle L \:=\: \frac{1}{2}\left(L + \frac{2}{L}\right)$ . . . fine

but now it says that this can be rewritten as $\displaystyle L^2 = 2$
and that the limit is $\displaystyle \sqrt{2}$. .How?

We have: .$\displaystyle L \:=\:\frac{L}{2} + \frac{1}{L}$

Multiply by $\displaystyle 2L\!:\quad 2L^2 \:=\:L^2 + 2 \quad\Rightarrow\quad L^2 \:=\:2 \quad\Rightarrow\quad L \:=\:\sqrt{2}$

• Jun 1st 2009, 08:06 AM
HallsofIvy
Quote:

Originally Posted by pberardi
Hello,
I am looking at this recursion formula in my Calculus book.
x_n+1 = 1/2(x_n + 2/x_n)
It goes on to say that we can find the limit of this sequence by doing this:
L = 1/2(L + 2/L) fine
but now it says that this can be rewritten as L^2 = 2 and that the limit is the square root of 2. How?

Could someone please explain the last two steps? Thank you so much.

Multiply both sides of that equation by 2L to get rid of the fractions- $\displaystyle 2L^2= L^2+ 2$ which is the same as $\displaystyle L^2= 2$. That actually has two roots. In order to determine whether the limit is $\displaystyle \sqrt{2}$ or $\displaystyle -\sqrt{2}$ for a specific sequence you must also be given a "starting" value of $\displaystyle x_0$. Are you given something like "$\displaystyle x_0= 1$".

In fact, it should be clear that if $\displaystyle x_n$ is positive, then $\displaystyle x_{n+1}= (1/2)(x_n+ 1/x_n)$ is also positive while if $\displaystyle x_n$ is negative, then $\displaystyle x_{n+1}= (1/2)(x_n+ 1/x_n)$ is also negative.
That is, if $\displaystyle x_0$ is positive, the limit is $\displaystyle \sqrt{2}$ and if $\displaystyle x_0$ is negative, the limit is $\displaystyle -\sqrt{2}$.

By the way, they get that original formula by arguing that if $\displaystyle \lim_{x\to \infty} x_n$ exists then you can call that limit L and use the laws of limits to argue that $\displaystyle lim x_{n+1}= (1/2)(lim x_n+ 1/lim x_n)$ and because "$\displaystyle x_{n+1}$" is just the same sequence renumbered, each of those limits is L: $\displaystyle L= (1/2)(L+ 1/L)$.

To be rigorous, you would still have to show the limit exists.

(Blast! Soroban got in ahead of me again!)
• Sep 20th 2009, 04:52 AM
naught101
Cool, I'm doing a variation of this question for uni. It's starting to come together for me now. The actual question is:
$\displaystyle x_{n+1} = \frac{1}{2}(x_n + \frac{\alpha}{x_n})$
and priors are $\displaystyle \alpha > 0$ and $\displaystyle x_1 >\sqrt{\alpha}$

My main question is how does the substitution for L work? You substitute L for x_(n+1) and for x_n? I guess that requires the assumption that the sequence is converging, right? If not, why not? If so, how do you prove monotonic decrease and find the limit, given the series is recursive?