Some questons about recurrence sequences (using a problem).

Question

A quick doubt, lets study the recurrence sequence:

$A_{n+1}=(4A_n +2)/A_n+3$;

$A_{0}<-3$

First of all i do:

$A_{n+1}-A_{n}<0$

If this is true i can say that $A_n$ decrease. This is true for those $A_n$ values:

$-3>A_n>-1$

$A_n>2$

And false (so $A_n$ increase) for those $A_n$ values:

$A_n<-3$

$-1<A_n<2$

the case $A_n<-3$ interests me.

The limit $L$ can be $-1$ or $-2$ but i cannot say it exists for sure because $A_n$ is not limited and monotone for all the $A_n$ possible values. For example, the sequence can go from $A_n>2$ then decrease and go in $A_n<-3$ then again increase and fall in $A_n>2$ etc...

Another doubt comes from this fact:

It's ok to remove $-1$ from the possible values of $L$ because in this case the sequence still growing?

Anyways: It happens so many times that i know the sequence increase or decrease in an interval but i don't know if doing it it will fall in another interval where it starts decreasing or increasing and in this scenario i don't know how to demonstrate if it goes on some limit or just starts to "ping-pong" on different intervals.

Or in other words i don't know how many it decrease/increase so i cannot say if it will go out from the interval i'm considering.

Hopefully i was clear.

Answer 1

Assume for the moment that the recursive sequence converges. Then the limit would satisfy the quadratic equation $$ L(L+3)=4L+2\iff 0=L^2-L-2=(L-2)(L+1) $$ Take the negative fixed point $L=-1$ and consider the sequence $B_n=A_n+1$ or $A_n=-1+B_n$. Then $$ B_{n+1}=1+\frac{-4+4B_n+2}{-1+B_n+3}=\frac{5B_n}{B_n+2} $$ which tells that the iteration will move away from that fixed point with speed around $\frac52$ except in the case where $B_0=0$, $A_0=-1$, which is excluded.

For the second fixed point $L=2$ a similar consideration with $A_n=2+C_n$ gives $$ C_{n+1}=-2+\frac{4(2+C_n)+2}{C_n+2+3}=\frac{2C_n}{C_n+5} $$

Now if $A_0<-3$, then $C_0<-5$ and $C_1>0$ so that $0<C_{n+1}<\dfrac25C_n$ for $n>1$. Thus the sequence $(C_n)_n$ converges to $0$, in consequence $(A_n)_n$ to $2$.

Answer 2

If you suspect oscillating behavior, then apply the recursion twice, i.e., examine how $A_{n+2}$ depends on $A_n$.

In the case of fractions of linear terms one can fully linearize the problem by writing $A_n=P_n/Q_n$, $P_0=A_0$, $Q_0=1$ and using the one degree of freedom to extract from $$ \frac{P_{n+1}}{Q_{n+1}}=A_{n+1}=\frac{4A_n+2}{A_n+3}=\frac{4P_n+2Q_n}{P_n+3Q_n} $$ the linear system $$ \begin{bmatrix}P_{n+1}\\Q_{n+1}\end{bmatrix} = \begin{bmatrix}4&2\\1&3\end{bmatrix} \begin{bmatrix}P_{n}\\Q_{n}\end{bmatrix} $$ As the characteristic equation is $$ 0=z^2-7z+10=(z-2)(z-5) $$ the roots are $z_1=5$ and $z_2=2$ with eigenvectors $v_1=\binom{2}{1}$ and $v_2=\binom{1}{-1}$.

The solution will thus have the form $P_n=2c_15^n+c_22^n$, $Q_n=c_15^n-c_22^n$, $Q_0=1\implies c_2=c_1-1$, $P_0=A_0\implies c_1=\frac13(A_0+1)$ and thus $$ A_n=\frac{2(A_0+1)5^n+(A_0-2)2^n}{(A_0+1)5^n-(A_0-2)2^n} =\frac{2(A_0+1)+(A_0-2)(\frac25)^n}{(A_0+1)-(A_0-2)(\frac25)^n} $$ Which will in all but one exceptional case (where $c_1=0$, i.e., $A_0=-1$) converge to $2$.