Sequence that converges to a square root

800 Views Asked by At

Let there be any two numbers $x$ and $y$, where $x,y \in \mathbb R$ and $y \neq -1$.

Consider a sequence where $$a_1 = \frac{y+x}{y+1}$$ and $$a_{n} = \frac{a_{n-1}+x}{a_{n-1} + 1}.$$

For example, when $x=5$ and $y=50$: $$a_1 = \frac{50+5}{50+1} = \frac{55}{51},$$$$a_{2} = \frac{\frac{55}{51}+5}{\frac{55}{51}+1} = \frac{310}{106},$$$$a_3 = \frac{\frac{310}{106}+5}{\frac{310}{106}+1} = \frac{840}{416},$$$$a_4 = \frac{\frac{840}{416}+5}{\frac{840}{416}+1} = \frac{2920}{1256},$$ et cetera. The result approaches very quickly $\sqrt 5$.

My question is: does this sequence always converge to $\sqrt x$?

1

There are 1 best solutions below

0
On BEST ANSWER

Write the recurrence relation as:

$$a_{n}=1+\frac{x-1}{1+a_{n-1}}=1+\cfrac{x-1}{2+\cfrac{x-1}{2+\cfrac{x-1}{1+a_{n-3}}}}$$

Writing the 'infinite' representation (formally so far) for the limit we have:

$$a_{ \infty} =1+\cfrac{x-1}{2+\cfrac{x-1}{2+\cfrac{x-1}{2+\dots}}}$$

For $x=2$ we have:

$$a_{ \infty} =1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\dots}}}=\sqrt{2}$$

This is a simple continued fraction, which is known to converge for sure if the partial denominators $b_k>0$ and their value doesn't decrease faster than $1/k$. In this case they are constant, so it converges.

The limit of $\sqrt{2}$ is well known too, and can be shown by the same method wilkersmon suggested in the comments.


For a general $x>1$ we also have:

$$\sqrt{x} =1+\cfrac{x-1}{2+\cfrac{x-1}{2+\cfrac{x-1}{2+\dots}}}$$

The convergence can be shown by transforming the continued fraction into the form of a 'simple' continued fraction:

$$\sqrt{x} =1+\cfrac{1}{\frac{2}{x-1}+\cfrac{1}{2+\cfrac{1}{\frac{2}{x-1}\cfrac{1}{2+\cfrac{1}{\frac{2}{x-1}+\dots}}}}}$$

Since the partial denominators do not decrease on average, the CF converges.

For $x < 1$ the case for convergence is a little more complicated (because the partial denominators become negative), but we can just consider $1/\sqrt{x}$ instead.


This continued fraction for square roots is referenced at Wikipedia https://en.wikipedia.org/wiki/Continued_fraction.