# Studying the convergence of a recurrence relation

I'm studying the convergence of the recurrence relation with a fixed $$r > 0, r \in \Bbb{R}$$ with $$u_{n+1}$$ given by $$u_{n+1} = \frac{u_{n}^2}r + 1$$ and $$u_0 = 0$$.

It can be shown that $$u_n > 1$$ for all $$n \in \Bbb{N}$$ and then $$(u_n)$$ is increasing.

By studying that happens when we pass to the limit, we can use the quadratic formula to show that $$l$$ exists only when $$r\geq4$$ (this is when the determinant $$1-\frac{4}r$$ is zero). Then, as $$(u_n)$$ is increasing and unbounded, we have $$u_n \longrightarrow \infty$$.

Now, here's where I've started to get a little bit confused. I can see inherently that $$l$$ would be equal to $$\frac{r}2-\frac{r}2\sqrt{1-\frac{4}r}$$, but my question is on how to show this for any $$r\geq4$$ and any $$n \in \Bbb{N}$$. Would there be a way to show this by induction? Is there some other way to simplify this value or simplify the proof that would make this upper bound easier to show?

• Why $\frac1r$ instead of $r$ ?
– user65203
Nov 17, 2018 at 13:43
• Quadratic formula ? Why ???
– user65203
Nov 17, 2018 at 13:53
• @YvesDaoust Sorry, I wrote the relation incorrectly, I've edited it to reflect what I meant. Nov 17, 2018 at 13:55
• @DavidC.Ullrich Sorry, thank you, I didn't reflect the initial condition properly. I'm focusing specifically on the case $u_0 = 0$. Nov 17, 2018 at 13:58

First, I'd check the limit. If we assume that there is a limit $$u_{l}$$, then:

\begin{align*} u_{l} &= \frac{u_l^2}{r} + 1 \\ 0 &= u_l^2 - ru_l + r \end{align*}

So the quadratic formula says this:

$$u_l = \frac{r \pm \sqrt{r^2-4r}}{2} = \frac{r}{2} \pm \frac{r}{2}\sqrt{1 - \frac{4}{r}}$$

As you've noted, starting from $$u_0 = 0$$, we'd expect convergence to the lower limit, $$\frac{r}{2} - \frac{r}{2}\sqrt{1 - \frac{4}{r}}$$. Let's call that lower limit $$b$$, and define the series $$t_n$$ as $$t_n = b - u_n$$, and see where the recurrence relation given takes us:

\begin{align*} b - t_{n+1} &= \frac{(b-t_n)^2}{r} + 1 \\ br - rt_{n+1} &= (b-t_n)^2 + r \\ br - rt_{n+1} &= b^2 - 2 b t_n + t_n^2 + r \\ - rt_{n+1} &= t_n(1 - 2b) + b^2 - br + r \end{align*}

But by construction, we know that $$b^2 - br + r = 0$$, so:

\begin{align*} - rt_{n+1} &= t_n(1 - 2b) + 0 \\ t_{n+1} &= t_n\frac{(2b - 1)}{r} \end{align*}

And from there, it's straightforward that $$t_n \to 0$$, and therefore $$u_n \to b$$.

In general in these types of problems, I find that once you have a putative limit reframing the problem in terms of a new series defined as (limit - old series) usually makes the problem easier.

• Just so no one's confused: there's no value we could start at except the top quadratic solution that would lead us to a limit of the top quadratic solution. (Since that's an unstable point) But starting from 0, when $r > 4$, definitely leads to the bottom quadratic solution. Nov 17, 2018 at 14:29

If the sequence converges, we have

$$u_{\infty}=\frac{u_{\infty}}r+1$$ or

$$u_{\infty}=\frac r{r-1}.$$

Obviously, convergence is impossible for $$r<1$$ as the terms remain positive. Then for $$r>1$$,

$$u_{n+1}-u_\infty=\frac{u_n}{r}+1-u_\infty=\frac{u_n-u_\infty}r.$$

By induction,

$$u_n-u_\infty=(u_0-u_\infty)r^{-n}.$$

• A more colorful proof of convergence for $r>1$ would mention that $t\mapsto t/r+1$ is a strict contraction... Nov 17, 2018 at 13:56