# Limit for a Recurrence Relation

How I can find a limit for this recursively defined sequence?

$$a_0>0, a_{n+1}=\frac{a_{n}+2}{3a_{n}+2}$$

I'm particularly interested in answers involving concepts like contractive sequences and fixed points.

Many thanks.

-

There are two fixed points, $\frac23$ and $-1$. Let's look at the stability near each of these.

Let $$f(x)=\frac{x+2}{3x+2}\tag{1}$$ Then $$f'(x)=-\frac43\frac1{(3x+2)^2}\tag{2}$$ Since $f'\left(\frac23\right)=-\frac13$ and $f'(-1)=-\frac43$, $\frac23$ is a stable fixed point, $|f'(x)|\lt1$, and $-1$ is an unstable fixed point, $|f'(x)|>1$.

Let's investigate the stable fixed point. The recursive definition centered on $\frac23$ becomes $$\left(a_n-\tfrac23\right)=-\frac{\left(a_{n-1}-\tfrac23\right)}{3\left(a_{n-1}-\tfrac23\right)+4}\tag{3}$$ Note that if $a_{n-1}\gt0$, then $3\left(a_{n-1}-\tfrac23\right)+4\gt2$. Thus, $(3)$ implies that $$\left|a_n-\tfrac23\right|\lt\tfrac12\left|a_{n-1}-\tfrac23\right|\tag{4}$$ $(4)$ guarantees convergence.

-
Perhaps this is the most oriented towards dynamical systems amongst all answers. Thanks. May I ask you: A) How you were able to find the fixed points? I guess from solving the quadratic equation; but WHY roots of the equation have to be fixed points? B) Why you assume these fixed points as potential limits? C) What about finding 2+ stable fixed points? They would be limits for some subsequences whilst the main sequence would oscillate? C) Any connection whit lim sup/inf? D) These things are fascinating. May I ask you some link to investigate further?? Thanks a lot!! –  MadHatter Jan 22 '13 at 17:02
@UzzoloDivendetta: A) fixed points are those which satisfy $f(x)=x$, so I just solved $\frac{x+2}{3x+2}=x$ to get the fixed points. B) If $f$ is continuous at $x_\infty=\lim\limits_{n\to\infty}x_n$, then $\lim\limits_{n\to\infty}f(x_n)=f\left(\lim\limits_{n\to\infty}x_n\right) =f(x_\infty)$. C) If there are more than one stable fixed point, one goal would be to find out what regions converge to each fixed point, and which regions don't lead to convergence. D) One problem that I spent some time on in college was finding the Fermat Point. –  robjohn Jan 22 '13 at 18:34
By the virtue of wich theorem you gave answer B? –  MadHatter Jan 22 '13 at 18:55
One last thing: generally speaking, what significance we can infer to the ratio of two successive term of a sequence? We can naively think "if this tends to 1, the sequence has limit". But there exist sequences for wich this is false... –  MadHatter Jan 22 '13 at 19:11
@UzzoloDivendetta: B) follows from the definition of continuity. If the limit of the ratio of two consecutive terms is not $1$, the sequence does not converge. The ratio of the terms of the sequence $a_n = n$ tends to $1$, but the sequence does not converge. –  robjohn Jan 22 '13 at 19:37

A little playing shows that the limit "should" be $\frac{2}{3}$. So it is natural to compute $a_{n+1}-\frac{2}{3}$. We get $$a_{n+1}-\frac{2}{3}=\frac{a_n+2}{3a_n+2}-\frac{2}{3}=\frac{\frac{2}{3}-a_n}{3a_n+2}.$$ Thus $$\left|a_{n+1}-\frac{2}{3}\right|=\left|a_n-\frac{2}{3}\right|\frac{1}{3a_n+2}.$$ In particular, $$\left|a_{n+1}-\frac{2}{3}\right|\lt \frac{1}{2}\left|a_n-\frac{2}{3}\right|.$$ So with each iteration our distance from $\frac{2}{3}$ shrinks by a factor of at least $\frac{1}{2}$. It follows that $\lim_{n\to\infty}a_n=\frac{2}{3}$.

-
Ok, got it. Look, by your last inequality you are verifying simply if it is a contractive sequence, right? Is this a suffcient (and perhaps necessary) condition to guarantee convergence? –  MadHatter Jan 22 '13 at 19:19
Sure, there was the explicit $|a_{n+1}-L|\lt (1/2)|a_n-L|$. You can also look at the derivative of $(x+2)/(3x+2)$. see where it has absolute value below $1$. The string of comments is getting long, system is objecting. Will delete most of mine, since you know the contents. –  André Nicolas Jan 22 '13 at 19:30
So, to say that the (absolute value of) the derivative at the the being <1 is a sufficient condition for the point to be a limit. Is this correct? –  MadHatter Jan 23 '13 at 10:00

Use the recurrence relation

$$a_{n+1} - a_{n} = \frac{a_n +2 }{ 3 a_n +2} - \frac{a_{n-1} +2}{3 a_{n-1} +2 } = \frac{4(a_{n-1} -a_{n})}{(3 a_{n-1} +2)(3 a_n +2)}.$$

Since $$3 a_n = 3 \frac{a_{n-1} +2 }{3 a_{n-1} +2} > 1 + \frac{1}{a_{n-1}+1} >1, \quad\forall n\geq 1,$$

it follows that $$|a_{n+1} - a_{n}| < \frac{4}{9} |a_{n} - a_{n-1}|.$$

Iteration gives $$|a_{n+1} - a_{n}| < \left(\frac{4}{9}\right)^n |a_{1} - a_{0}|.$$

The series $\sum_{n=1}^\infty (a_{n+1}-a_n)$, of positive terms, is dominated by the convergent series $|a_1-a_0| \sum_{n=1}^\infty (4/9)^n$ and so converges. We have $\sum_{n=1}^\infty (a_{n+1}-a_n)= \lim_{n\to \infty} a_n - a_1$ which shows that the limit exists.

Then, to find to fixed points we can pass to the limit in the recurrence relation $$a_{\infty}= \frac{a_{\infty}+2}{3 a_{\infty} +2},$$

which leads to $a_{\infty}= 2/3.$

-
I suppose this does satisfy my need for an argument involving contractions. Thanks. How I can find fixed point(s), if any? –  MadHatter Jan 21 '13 at 22:49
$$a_{n+1} - a_{n} = \frac{a_n +2 }{ 3 a_n +2} - \frac{a_{n-1} +2}{3 a_{n-1} +2 } = \frac{4(a_{n-1} -a_{n})}{(3 a_{n-1} +2)(3 a_n +2)}$$ Isn't it? And then how did you get inequality $$|a_{n+1}-a_n|\leq\frac{2}{3}|a_n-a_{n-1}|$$ ? –  Norbert Jan 21 '13 at 23:01
@Norbert oh you are right! thanks a lot! I assumed that they're greater than 1, I will fix it. –  беркай Jan 21 '13 at 23:04
Inequality $$|a_{n+1}-a_n|\leq\frac{4}{9}|a_n-a_{n-1}|$$ doesn't follow from the corrected first line. –  Norbert Jan 21 '13 at 23:14
@Norbert OK! but I cannot see what's wrong with it, can't you help? –  беркай Jan 21 '13 at 23:38

$1$. First show that $a_n \in (0,1)$ using induction.

$2$. Now if $a_0 < \dfrac23$, using induction, show that $a_n$ is a monotone increasing sequence bounded above by $\dfrac23$.

$3$. $\vert \vert \vert^{ly}$, if $a_0 > \dfrac23$, using induction, show that $a_n$ is a monotone decreasing sequence bounded below by $\dfrac23$.

$4$. Now recall the completeness of $\mathbb{R}$/ monotone sequence theorem, to conclude that the limit exists.

$5$. Now make use of limit laws to show that if $\lim_{n \to \infty} a_n = L$, then $$L = \dfrac{L+2}{3L+2}$$

$6$. Solve the quadratic to get that $L = \dfrac23$.

-
Awesome answer. Specifically, where the quadratic equation is arising from? And what about "contractive" methods? Thanks! –  MadHatter Jan 21 '13 at 22:47
@UzzoloDivendetta $L = \dfrac{L+2}{3L+2}$ gives rise to the quadratic equation $3L^2 + 2L = L+2 \implies 3L^2 + L - 2 =0$. Now since $a_n >0$, we have $L > 0$ which gives us $L = \dfrac23$. As for contractive methods, беркай provides a neat answer. –  user17762 Jan 21 '13 at 22:49
Ehm, |||^ly is a mistyping or a specific symbol? –  MadHatter Jan 21 '13 at 22:54
@UzzoloDivendetta I use $\vert \vert \vert^{ly}$ to mean similarly. Though, I am not sure if this is a universal notation. –  user17762 Jan 21 '13 at 22:55
Oh, ok.. Useful to know! ;-) –  MadHatter Jan 21 '13 at 22:56

Fix $c\in(0,3^{-1})$ and show that the map $$\varphi_c:[c,+\infty)\to[c,+\infty):x\mapsto\frac{x+2}{3x+2}$$ is well defined and what is more $$|\varphi_c(x)-\varphi_c(y)|\leq\frac{4}{(3c+2)^2}|x-y|$$ Hence you can apply Banach fixed point theorem to show that $\varphi_c$ have unique fixed point on $[c,+\infty)$ and this is point is $2/3$.

Since this fixed point is the same for all $c$ and $f|_{[c,+\infty)}=\varphi_c$, then $f$ has unique fixed point on $(0,+\infty)$

-
Your argument actually appears to be one of the most interesting. But some assumptions are still unclear; for example, why you pick c in (0,1/3)? Apart from this specific point, can you give me some links where I can investigate these approaches further? Thanks. –  MadHatter Jan 22 '13 at 16:53
We choose $c\in(0,1/3)$ because we want $\varphi_c$ to be well defined. I.e. we want $\varphi_c$ to map $[c,+\infty)$ into $[c,+\infty)$. This happens if $0<c<1/3$. –  Norbert Jan 22 '13 at 17:21