# Help me understanding logic behind limits of recurence relations

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!

-

## 3 Answers

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

-
Hey man, thanks for correcting me and nice explaination about those starting values. In fact i have one more doubt about proving monotonoicity. You said that if $1<a_n<3$ then $1<a_{n+1}<a_n<3$, what about if we have 3 fixed points? Which to pick? I'm so confused about it... Sometimes we can do $\frac{a_{n+1}}{a_n} < 1$ to prove it's decreasing, right? But sometimes, like in this case, we end up with some fixed points. Please explain what to do, like to 5 years old, confused kid. I'd appreciate it so much. – Spinach Dec 26 '13 at 15:24
@Chris: In general what I'd do is chop the x-axis into intervals with endpoints at each fixed point and whenever the function to iterate has a discontinuity (such as $x=4$ in this case). Then there's some hope (it's not quite a certainty) that we can prove that the function has "similar" behavior within any one of the intervals. So the first one to investigate would be the one that $a_0$ is in. – Henning Makholm Dec 26 '13 at 15:36
@Chris: Yes, sometimes the ratio $a_{n+1}/a_n$ is an easier way to prove motonicity. It depends on the exact function you're investigating which one is easiest -- sometimes there's more than one way that works; at other times only one of them does. And sometimes (hopefully not in homework problems) there's nothing that seems to work at all. The best general advice I can give is try a variety of approaches and hope one of them will work. After some time you may get enough experience to have an idea what to try first depending on how the functions look. – Henning Makholm Dec 26 '13 at 15:39
Okay, thanks a lot :-) – Spinach Dec 26 '13 at 15:43

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

-
I agree that drawing a graph is very helpful for this kind of problems. But beware that the function in this drawing is qualitatively different from the one in the question! – Henning Makholm Dec 26 '13 at 15:50
@HenningMakholm: Yes, it is different, but the same method works (try "plot[x, 3/(4-x), {x,-5,5},{y,-5,5}]" in WolframAlpha and then argue the same way). I have suggested this drawing only because it better explains the method, and it was the only drawing of this kind I found on the web ;) – tour Dec 26 '13 at 16:19

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$

-
You are missing (-) before polynomial. :-) Thanks for your analysis. – Spinach Dec 26 '13 at 15:33
oops! I need coffee badly :-) – user44197 Dec 26 '13 at 15:35
Whoops, i think i need coffee, not you, you just reversed dominator instead of putting (-) in front of whole fraction :-D forgive me. – Spinach Dec 26 '13 at 15:42