Iteration on sequences

Question

I am trying to find a general formula for this sequence, in order to find its limit (has to be this way):

$$X_{k+1} = \frac {X_k} 2 + \frac 1 {X_k}$$

I cannot get a grasp on it; after $2$ or $3$ iterations, the sequence gets huge and I don't see the pattern. Any help is greatly appreciated!

Answer 1

If $X_0=\sqrt 2$, then the sequence is constant, so we can assume $X_0\not = \sqrt 2$. We may also assume that $X_0>0$, as the negative case is the same.

Let $X_0=\sqrt 2\cdot\frac {r+1}{r-1} $, or $r=\frac{X_0+\sqrt2}{X_0-\sqrt2}$, then the closed form is $X_k=\sqrt 2\cdot\frac {r^{2^k}+1}{r^{2^k}-1}$. The way to get the closed form is as follows.

Dividing by $\sqrt 2$: $$\frac {X_{k+1}}{\sqrt 2}=\frac 12(\frac {X_{k}}{\sqrt 2}+\frac {\sqrt 2}{X_{k}})$$

Substituting $\frac {X_{k}}{\sqrt 2}=S_k+1$: $$S_{k+1}+1=\frac 12 \cdot(S_k+1+\frac 1{S_k+1})$$ $$S_{k+1}=\frac 12 \cdot(S_k-1+\frac 1{S_k+1})$$ $$S_{k+1}=\frac 12 \cdot\frac {S_k^2}{S_k+1}$$ Taking the inverse: $$\frac 1{S_{k+1}}=2 \cdot\frac {S_{k}+1}{S_k^2}$$ $$\frac 1{S_{k+1}}= 2\cdot (\frac 1{S_{k}})^2+2\cdot \frac 1{S_{k}}$$ Completing the square: $$\frac 1{S_{k+1}}+\frac 12=2\cdot(\frac 1{S_{k}}+\frac 12)^2$$ $$\frac 2{S_{k+1}}+1=(\frac 2{S_{k}}+1)^2$$ This means each term is the square of the previous term, which we can denote as $\frac 2{S_{k}}+1=r^{2^{k}}$. Substituting everything back into $X_k$ then we have the close form.

Proving that the closed form is actually correct: \begin{align} \frac {X_k}2+\frac 1{X_k} &=\frac 1{\sqrt2} \cdot (\frac {r^{2^k}+1}{r^{2^k}-1}+\frac {r^{2^k}-1}{r^{2^k}+1})\\ &=\frac 1{\sqrt2} \cdot \frac {(r^{2^k}+1)^2+({r^{2^k}-1})^2}{(r^{2^k}-1)({r^{2^k}+1})} \\ &=\frac 1{\sqrt2}\cdot \frac {r^{2^{k+1}}+2r^{2^k}+1+r^{2^{k+1}}-2r^{2^k}+1}{r^{2^{k+1}}-1}\\ &=\sqrt 2\cdot \frac {r^{2^{k+1}}+1}{r^{2^{k+1}}-1}\\ &=X_{k+1} \end{align}

Answer 2

If the sequence converges, it must converge to an $x$ such that

$$x=\frac x2+\frac1x$$ or $$x^2=2.$$

Then with $x_k:=y_k+\sqrt2$,

$$y_{k+1}+\sqrt 2=\frac{y_k+\sqrt2}2+\frac1{y_k+\sqrt2}$$ and

$$y_{k+1}=\frac{y_k^2}{2(y_k+\sqrt2)}\le\frac{y_k^2}{2\sqrt2}.$$

You easily see that starting from $y_0<1$, you get a (quickly) decreasing sequence with limit $0$.