1
$\begingroup$

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?

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Nov 17, 2018 at 14:29
0
$\begingroup$

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

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

You must log in to answer this question.

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