# Existence of limit for sequence $x_n=\frac12\left(x_{n-1}+\frac8{x_{n-2}}\right)$ with initial values $x_0=5,x_1=10$

Let $$x_0=5,x_1=10,$$ and for all integers $$n\ge2$$ let $$x_n=\frac12\left(x_{n-1}+\frac8{x_{n-2}}\right).$$ By induction, we have $$\forall m\in\mathbb Z_{\ge0}\enspace x_m>0,$$ so we can avoid division by $$0$$ and the sequence is well-defined.

According to a Math GRE practice problem, the limit exists. How can we prove that? Note that, if we assume the limit exists, then we can show it equals $$\sqrt8,$$ but finding the value of the limit is not my goal here.

My work: We can compute $$x_2=5.8,x_3=3.3,$$ which are strictly between $$4/3$$ and $$6,$$ and then, assuming an inductive hypothesis, for all integers $$n\ge4$$ we have $$4/3 and $$4/3<8/x_{n-2}<6,$$ so that $$4/3 We can probably compute more values of $$x_n$$ to get tighter bounds, but I don't see how to actually show convergence.

• Is "we can divide by $0$" in the second line a typo? Because I'm sure you'll agree that you can't divide by $0$ Jul 24, 2020 at 12:18
• @xFioraMstr18 If the limit exists and is some number $L$, it must satisfy $L=\frac 12 (L+\frac 8L)$. Since $L>0$, you must have $L=2 \sqrt{2}$. Regarding existence, maybe you can show the sequence is Cauchy? Jul 24, 2020 at 12:21
• @PierreCarre you're perfectly right, the sequence is on the wiki/Cauchy_sequence, except having $2$ instead of $8$. Jul 24, 2020 at 12:30
• Let $y_n=x_n/\sqrt8$, to get rid of the 8. Then linearising to $z_n=\frac12(z_{n-1}-z_{n-2})$, the characteristic equation has roots $\frac14(1\pm i\sqrt7)$ so it goes above and below the limit fairly irregularly Jul 24, 2020 at 12:42
• $y_n=1+z_n$, then $z_{n+1}=\frac12(z_n+\frac1{1+z_{n-1}}-1)=\frac12(z_n-z_{n-1}+\frac{z_{n-1}^2}{1+z_{n-1}})$ then i neglect the term with $z_{n-1}^2$ in the numerator. The solution to the linearised equation is $A((1+i\sqrt7)/4)^n+B((1-i\sqrt7)/4)^n$, the absolute values shrink by a factor $\sqrt2$, not grow by a factor $e^{1/4}$ Jul 24, 2020 at 14:05

Let $$x_{n+1}=\tfrac{1}{2}(x_n+\frac{a}{x_{n-1}})$$

Then for $$d_n=x_n-\sqrt{a}$$, \begin{align} x_{n+1}-\sqrt{a}&=\tfrac{1}{2}(x_n-\sqrt{a})+\frac{a}{2}\left(\frac{1}{x_{n-1}}-\frac{1}{\sqrt{a}}\right)\\ d_{n+1}&=\tfrac{1}{2}d_n-\frac{\sqrt{a}}{2}\frac{d_{n-1}}{d_{n-1}+\sqrt{a}}=\tfrac{1}{2}d_n-\frac{1}{2}\frac{d_{n-1}}{\frac{d_{n-1}}{\sqrt{a}}+1}\\ \end{align}

So if $$|d_{n-1}|<\sqrt{a}/3$$, $$|d_{n+1}|\le \begin{cases}\tfrac{1}{2}|d_n|,&d_{n-1}d_n>0\\ \frac{1}{2}|d_n|+\frac{3}{4}|d_{n-1}|,&d_{n-1}d_n<0\end{cases}$$ Since the worst case cannot happen twice in succession, we must have $$|d_{n+2}|\le\tfrac{1}{4}|d_n|+\tfrac{3}{8}|d_{n-1}|$$

This recurrence inequality can be solved, $$|d_n|\le A|r_1|^n+B|r_2|^n+C|r_3|^n\to0$$ since $$r_1\approx0.84$$, $$|r_2|=|r_3|\approx0.67$$.

Hence, as long as some $$d_k$$ comes close enough to $$\sqrt{a}$$, $$x_n\to\sqrt{a}$$. (In fact, the sequence may converge to $$-\sqrt{a}$$, e.g. $$x_0=x_1=-1$$ for $$a=8$$. )

• If $d_{n-1}$ is near $-\sqrt a/3$, the term is bounded by $\frac34|d_{n-1}|$, not $\frac38|d_{n-1}|$ Jul 24, 2020 at 14:34
• @Empy2 You're right. Jul 24, 2020 at 15:38
• @Empy2 Should be fixed now. Jul 24, 2020 at 18:01
• I think you need something like $Ar_1^n+B|r_2|^n+C|r_3|^n$ (absolute values). Jul 24, 2020 at 19:57
• @xFioraMstr18 Thanks! Corrected. Jul 25, 2020 at 6:48

As in my comments, let $$y_n=x_n/\sqrt8=1+z_n$$. Then $$z_{n+1}=\frac12(z_n-z_{n-1}+\frac{z_{n-1}^2} {1+z_{n-1}})\\ =\frac14\left(-z_{n-1}-z_{n-2}+2\frac{z_{n-1}^2}{1+z_{n-1}}+\frac{z_{n-2}^2}{1+z_{n-2}}\right)$$ So if $$|z_{n-1}|$$ and $$|z_{n-2}|$$ are both at most $$c$$ which is less than $$1/4$$ then $$|z_{n+1}| \le \frac c4+\frac c4 +\frac{3c^2}{4(1-c)}\lt \frac34c$$

• I changed the the constant from $1/13$ to $1/4$ so that we need to compute only 5 values ($x_3,x_4,x_5$ are within $\sqrt8/4$ of $\sqrt8$) instead of 8 values ($x_6,x_7,x_8$ are within $\sqrt8/13$ of $\sqrt8$). Jul 24, 2020 at 19:53
• That turns the expression in the middle into $c/4+c/4+1c$, not $c/4+c/4+c/4$ Jul 24, 2020 at 19:59
• Oh, your $3c^2/(1-c)$ could have been improved to $3c^2/(4(1-c)).$ It looks like you forgot the $1/4$ factor from outside the parentheses. The current edit should be correct now. Jul 24, 2020 at 20:11

it is easy to show that $$|x_{n}-A|<\epsilon$$ for all the $$x_{n}$$ for a given $$A$$. such that $$A-\epsilon $$-A-\epsilon<-x_{n}<-A+\epsilon$$ $$\frac{8}{A+\epsilon}<\frac{8}{x_{n}}<\frac{8}{A-\epsilon}$$ use equation $$x_{n}=\frac{1}{2}(x_{n-1}+\frac{8}{x_{n-2}})$$ we have $$x_{n}-x_{n-1}=\frac{1}{2}(-x_{n-1}+\frac{8}{x_{n-2}})$$ using inequatity (2)(3) we have $$\frac{1}{2}(-A-\epsilon+\frac{8}{A+\epsilon}) since $$\epsilon< we use the expansion and keep the first term we get: $$\frac{1}{1+\epsilon}=1-\epsilon+O(\epsilon^{2})$$ we get: $$\frac{1}{2}(-A-\epsilon+\frac{8}{A(1+\frac{\epsilon}{A})})

$$\frac{1}{2}(-A-\epsilon+\frac{8}{A}(1-\frac{\epsilon}{A}))

$$\frac{1}{2}(-A+\frac{8}{A}-\epsilon-8\frac{\epsilon}{A^{2}})

Also, we know that $$|a+b|<|a|+|b|$$ and $$|a-b|<|a|+|b|$$, such that

$$|x_{n}-x_{n-1}|<\frac{1}{2}(|-A+\frac{8}{A}|+|\epsilon+8\frac{\epsilon}{A^{2}}|)$$

if we set $$A=\sqrt{8}$$

we get: $$|x_{n}-x_{n-1}|<\frac{1}{2}(|-\sqrt{8}+\frac{8}{\sqrt{8}}|+|\epsilon+8\frac{\epsilon}{8}|)$$

$$|x_{n}-x_{n-1}|<|\epsilon|$$

which means that $$x_{n}$$ converge to A