# Convergence of recursive scheme

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.

• 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. Jul 15 '18 at 13:03

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