Help me understanding logic behind limits of recurence relations

Question

I was trying to understand how limits of recurence relations are working. I have one.

$$a_0 = \dfrac32 ,\ a_{n+1} = \frac{3}{4-a_n} $$

So, from what i know, if this recurence relation has a limit, it have to be bounded and monotonous. To check if it's bounded i have to calculate $$\lim_{x \rightarrow \infty} \frac{3}{4-x}$$ and it goes to 0, so it's bounded.

Now to check if it's monotonous i have to check if $$a_{n+1} - a_n$$ is monotonous.

$$a_{n+1} - a_n = \frac{3}{4-a_n} - a_n = - \frac{(a_n-3)(a_n-1)}{(a_n-4)}$$ This expression is monotonous ( decreasing ) but only starting at x = 5. Is it enough to say that this is monotonous?

If it is. We know that $$\lim_{n \rightarrow \infty} a_n = \lim_{n \rightarrow \infty} a_{n+1} $$

So we calculate it $$L = \frac{3}{4-L}$$ and end up with $$L^2 - 4L + 3 = 0 \rightarrow (L-1)(L-3) = 0$$ We know that the limit of this recurence relation can be 1 or 3. On our classes there always were some examples that had only 1 possible limit to choose. In this example we have decreasing sequence and $a_0 = \dfrac32$ then one possible limit is 1.

I was starting to check it... What if $a_0 = \dfrac12$? What if $a_0 = 5$ or $a_0 = 2$ it turns out that, no matter what starting value we have, sequence always goes to the same limit ( at least in this example ). Is it true for all recurence relations? You can check using wolframalpha clicking here and just manipulate with starting value. Please help me with this and explain those weird things. I'd be so thankful!

Answer 1

You have some conceptual mistakes right from the beginning.

So, from what i know, if this recurence relation has a limit, it have to be bounded and monotonous.

No, you have that the wrong way around. Every sequence that is bounded and monotonic has a limit, but there are sequences that have limits without being monotonic, such as $$ 2, \frac{1}{2}, \frac{5}{4}, \frac{7}{8}, \frac{17}{16}, \frac{31}{32}, \frac{65}{64}, \frac{127}{128} $$ (which is generated by the recurrence $x_{n+1}=\frac{3-x}{2}$ and has limit $1$, but alternately increases and decreases).

(The word is "monotonic", not "monotonous", by the way).

Now to check if it's monotonous i have to check if $a_{n+1}−a_n$ is monotonous.

Um, no, checking whether the sequence is monotonic is not the same as checking whether the sequence of first differences are monotonic.

Instead of trying to concoct a single test for montonoicity, it is better to think of it as asking two questions: Is is increasing? Is it decreasing?

In this case, you should be able to prove that if $a_n$ is between $1$ and $3$, then $a_{n+1}$ is smaller than $a_n$ and still between $1$ and $3$. So this case will continue holding forever, and the sequence is decreasing (which is one of the ways it can be monotonic). The same proof shows it is bounded.

(Why $1$ and $3$? Because those are the fixed points of the functions you're iterating, and I know from experience that the behavior of iterated functions change near such points -- effectively I have seen informally that the limit is probably going to be $1$, and I'm now trying to construct a proof that my hunch is right, not trying to feign stupidity and approach it with no hunches).

If you graph the function $y=\frac{3}{4-x}$ it is possible that the only proof you need here is some handwaving that says "for $1<x<3$ this graph is below the line $y=x$ and the function value is always in $[1,3]$".

Your computation of the fixed points now shows that the only limit that's consistent with being decreasing and staying between $1$ and $3$ is $1$, so $1$ must be the limit.

I was starting to check it... What if $a_0=1/2$? What if $a_0=5$ or $a_0=2$ it turns out that, no matter what starting value we have, sequence always goes to the same limit ( at least in this example ). Is it true for all recurence relations?

Even in this example, if $a_0=3$, then $a_n=3$ for all $n$, and therefore the limit is $3$. But otherwise, if $a_0\ne 4$ such that you avoid dividing by zero, the sequence does tend to $1$ no matter where you start it. To convince yourself of this you need to prove

• If $a_n<1$ then from that point on the sequence will increase monotonically towards $1$ (but never become greater than $1$).
• If $a_n>4$ then the next term in the sequence will be negative, and then we're in the previous case.
• If $3<a_n<4$, then the $a_n$ will get progressively further away from $3$ until you reach one that is larger than $4$, and then we're in the previous case.

There are also functions where you can end up with a sequence that grows without bound (such as $a_{n+1}=a_n^2$ if $a_0>1$), or sequences that stay bounded but don't tend to a limit -- such as $a_{n+1}=4a_n(a_n-1)$ which famously exhibits chaotic behavior when $a_0\in(0,1)$.

There are also recurrences that have several different attractive limits, depending on where you start them, such as $a_{n+1}=a_n+\sin a_n$.

Answer 2

You have most of your analysis right. Here is the complete discussion:

The two possible limits are $L=1$ and $L=3$ as you correctly point out.

Secondly, $$a_{n+1}-a_n = \frac{a_n^2 -4 a_n +3}{4 - a_n}$$

Between the two possible limits the numerator is negative, and outside the two possible limits it is positive. So we can make the following general observations

If $a_n < 1$ then $a_{n+1} > a_n$ (since numerator is $>0$, denominator $>0$)

If $1 < a_n < 3$ then $a_{n+1} <a_n$ (since numerator is $<0$, denominator $>0$)

If $3 < a_n < 4$ then $a_{n+1} > a_n$ (since numerator is $>0$, denominator $>0$)

If $4 < a_n $ then $a_{n+1} < 0$

So if you start to the left of $3$, $a_n \to 1$

If you start between $3$ and $4$, $a_n \to 4$ where the recurrence blows up, or you may go past $4$ in which case you down to next case.

If you start to the right of $4$, next number is less than zero and you back to the first case, i.e. $a_n \to 1$

Answer 3

To understand the behaviour of a sequence defined by $u_{n+1}=f(u_n)$ with given $u_0$ sometimes it helps to draw the graphs of $y=x$ and $y=f(x)$ on the same picture. Then it becomes possible to "draw" the sequence $u_n$. For example, when $f(x)=\sqrt{x}$ and $u_0=1/5$ the picture looks like this:

The main trick is that once $u_{n+1}$ is drawn, it is easy to find a point $u_{n+1}$ on the horisontal axis by means of "reflection" using the graph $y=x$. There are some more details on this on the page where I have have found this image: http://www.fmaths.com/recursivethinking/lesson.php

By the way, this example also demonstrates that the limit can depend on $u_0$. Namely, $$ \lim_{n\to \infty}u_n=\begin{cases}0, & u_0=0 \\ 1, & u_0\in(0,1], \\ +\infty, & u_0>1\end{cases} $$