6
$\begingroup$

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<x_{n-1}<6$ and $4/3<8/x_{n-2}<6,$ so that $4/3<x_n<6.$ We can probably compute more values of $x_n$ to get tighter bounds, but I don't see how to actually show convergence.

$\endgroup$
6
  • 2
    $\begingroup$ 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$ $\endgroup$
    – SeraPhim
    Jul 24, 2020 at 12:18
  • 2
    $\begingroup$ @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? $\endgroup$ Jul 24, 2020 at 12:21
  • $\begingroup$ @PierreCarre you're perfectly right, the sequence is on the wiki/Cauchy_sequence, except having $2$ instead of $8$. $\endgroup$ Jul 24, 2020 at 12:30
  • $\begingroup$ 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 $\endgroup$
    – Empy2
    Jul 24, 2020 at 12:42
  • 1
    $\begingroup$ $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}$ $\endgroup$
    – Empy2
    Jul 24, 2020 at 14:05

3 Answers 3

3
$\begingroup$

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$. )

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

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$

$\endgroup$
3
  • $\begingroup$ 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$). $\endgroup$ Jul 24, 2020 at 19:53
  • $\begingroup$ That turns the expression in the middle into $c/4+c/4+1c$, not $c/4+c/4+c/4$ $\endgroup$
    – Empy2
    Jul 24, 2020 at 19:59
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 24, 2020 at 20:11
0
$\begingroup$

it is easy to show that $|x_{n}-A|<\epsilon$ for all the $x_{n}$ for a given $A$. such that $$A-\epsilon<x_{n}<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})<x_{n}-x_{n-1}<\frac{1}{2}(-A+\epsilon+\frac{8}{A-\epsilon})$$ since $\epsilon<<A$ 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})})<x_{n}-x_{n-1}<\frac{1}{2}(-A+\epsilon+\frac{8}{A(1-\frac{\epsilon}{A})})$$

$$\frac{1}{2}(-A-\epsilon+\frac{8}{A}(1-\frac{\epsilon}{A}))<x_{n}-x_{n-1}<\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}})<x_{n}-x_{n-1}<\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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .