Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

5 Answers 5

up vote 3 down vote accepted

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.

share|improve this answer
    
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}$.

share|improve this answer
    
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.$

share|improve this answer
    
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}|$$ ? –  userNaN 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. –  userNaN 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$.

share|improve this answer
    
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)$

share|improve this answer
    
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$. –  userNaN Jan 22 '13 at 17:21
    
About fixed point theorem read this article –  userNaN Jan 22 '13 at 17:23
    
Uhm, is not perfectly clear. For example, what is the connection between my specific sequence and this choice of phi and (0,1/3). But let me read the article, perhaps I'll be able to ask more precisely. –  MadHatter Jan 22 '13 at 17:47
    
It is too long to explain all the details of mmy answer. –  userNaN Jan 22 '13 at 18:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.