0
$\begingroup$

I would like to see why below recursive scheme is convergent :

$x_{n+1}= \sqrt{\alpha\cdot x_n+\beta}$

Here, $\alpha>0$ and $\beta\in\mathbb{R}\setminus\left\{0\right\}$.

I tried something like:

$x_1=\sqrt{\alpha\cdot x_0+\beta}$

$x_2=\sqrt{\alpha\underbrace{\left(\sqrt{\alpha\cdot x_0+\beta}\right)}_{x_1} +\beta}$

$x_3= \sqrt{\alpha\underbrace{\left(\sqrt{\alpha\left(\sqrt{\alpha\cdot x_0+\beta}\right) +\beta}\right)}_{x_2}+\beta}$

$\cdots$

$x_{n+1}=\sqrt{\alpha\cdot x_n+\beta}$


Note 1 :

Also, I managed to boil down $x_2$ as:

$x_2=\sqrt{\alpha\cdot\left(\sqrt{\alpha\cdot x_0+\beta}\right)+\beta}\\$

or,

$x_2=\sqrt{\sqrt{\alpha^2\left(\alpha\cdot x_0+\beta\right)}+\beta}\\$

and further simplified as:

$x_2=\sqrt{\sqrt{\left(\alpha^3\cdot x_0+\alpha^2\beta\right)}+\beta}\\$


Note 2 :

And, with the same approach I did on $x_2$, also I simplified $x_3$ further as:

$x_3= \sqrt{\alpha\cdot \sqrt{\sqrt{\left(\alpha^3\cdot x_0+\alpha^2\beta\right)}+\beta}+\beta}$

or further simplified as:

$x_3= \sqrt{ \sqrt{\sqrt{\alpha^4\left(\alpha^3\cdot x_0+\alpha^2\beta\right)}+\beta}+\beta}$

that could be even more simplified by introducing the $\alpha^4$ inside the $\left(\cdot\right)$ as:

$x_3= \sqrt{ \sqrt{\sqrt{\left(\alpha^7\cdot x_0+\alpha^6\beta\right)}+\beta}+\beta}$


Note 3:

Based on (Note 1) and (Note 2), I could write my recursive scheme in a more compact ways as:

$x_1=\sqrt{\alpha\cdot x_0+\beta}$

$x_2=\sqrt{\sqrt{\alpha^3\cdot x_0+\alpha^2\beta}+\beta}\\$

$x_3= \sqrt{ \sqrt{\sqrt{\alpha^7\cdot x_0+\alpha^6\beta}+\beta}+\beta}$

$x_4= \sqrt{ \sqrt{ \sqrt{ \sqrt{ \alpha^{13}x_0+\alpha^{12}\beta }+\beta }+\beta }+\beta }$

$\cdots$

Now from here, I try to rewrite $x_1$, $x_2$, $x_3$ and $x_4$ such that they look to have a repeative term:

$x_1=\sqrt{\alpha^0\alpha\cdot x_0+\alpha^0\beta}$

$x_2=\sqrt{\sqrt{\alpha^2\alpha\cdot x_0+\alpha^2\beta}+\beta}\\$

$x_3= \sqrt{ \sqrt{\sqrt{\alpha^6\alpha\cdot x_0+\alpha^6\beta}+\beta}+\beta}$

$x_4= \sqrt{ \sqrt{ \sqrt{ \sqrt{ \alpha^{12}\alpha\cdot x_0+\alpha^{12}\beta }+\beta }+\beta }+\beta }$

and by factoring $\alpha^n$ out, inside the most inner square root we have:

$x_1=\sqrt{\alpha^{\overbrace{0}^{\left(1\cdot 0\right)}}\left(\alpha\cdot x_0+\beta\right)}$

$x_2=\sqrt{\sqrt{\alpha^{\overbrace{2}^{\left(2\cdot 1\right)}}\left(\alpha\cdot x_0+\beta\right)}+\beta}\\$

$x_3= \sqrt{ \sqrt{\sqrt{\alpha^{\overbrace{6}^{\left(3\cdot 2\right)}}\left(\alpha\cdot x_0+\beta\right)}+\beta}+\beta}$

$x_4= \sqrt{ \sqrt{ \sqrt{ \sqrt{ \alpha^{\overbrace{12}^{\left(4\cdot 3\right)}}\left(\alpha\cdot x_0+\beta\right) }+\beta }+\beta }+\beta }$

This, finally leads us to write a general iterative scheme as:

$x_{n}= \sqrt{ \cdots \sqrt{ \sqrt{ \sqrt{ \alpha^{n\left(n-1\right)}\left(\alpha\cdot x_0+\beta\right) }+\beta }+\beta \cdots }+\beta }$

Here, number of square roots is $n$.

Now, I need to see why the concluded iterative scheme is convergent.

$\endgroup$
1
  • $\begingroup$ Agreed. In this case, writing out the first few terms doesn't seem to help. So (as Surb shows) you need to prove convergence without using a general formula for the term. $\endgroup$
    – GEdgar
    Jul 15 '18 at 13:03
1
$\begingroup$

Such a sequence is always monotone and bounded. Let for example $\alpha >0$ and $\beta >0$. Let $\ell$ the unique solution to $\sqrt{\alpha x+\beta }=x$. If $x_0<\ell$, then $x_n$ will be increasing and upper-bounded by $\ell$ (prove by induction). If $x_0>\ell$, then the sequence will be decreasing and lower-bounded by $\ell$ (prove it by induction). If $x_0=\ell$, then it will be stationary. Try to adapt this when $\alpha <0$ and $\beta >0$ or when $\alpha <0$ and $\beta <0$ or when $\alpha >0$ and $\beta <0$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.