# Show convergence of recursive sequence and find limit value

Let $(a_n)_{n \in \mathbb N}$ be a recursive sequence. It is defined as $a_1=1, \quad a_{n + 1} = \frac{4a_n}{3a_n+3}$.

I have to show that the sequences converges and find a limit value.

To show convergence I was about to use the Cauchy criterum. Unfortunately I am quite confused here because of the recursive definition.

Question: How can I show show that the sequences converges and how can I find a limit value?

We already proved (in Show limit for recursive sequence by induction) that $a_n\geq {1\over 3}$ so $$a_{n+1}-a_n=a_n{1-3a_n\over 3a_n+3}\leq 0$$ so the sequence is decreasing and bounded so it is convergent. Say $a$ is it limit, then \begin{eqnarray*} a&=&\lim _{n\to \infty} a_{n+1} \\ &=& \lim _{n\to \infty} {4a_n\over 3a_n+3}\\ &=& {\lim _{n\to \infty}4a_n\over \lim _{n\to \infty}(3a_n+3)}\\ &=& {4a\over 3a+3} \end{eqnarray*} So we have to solve the equation $$a={4a\over 3a+3}\Longrightarrow 3a^2-a=0 \Longrightarrow a=0\;\; {\rm or}\;\; a=1/3$$ Since all members of sequence are $\geq {1/3}$ we have $$a ={1\over 3}$$

All the sequences fulfilling a recurrence relation of the form $a_{n+1}=\frac{A a_n + B}{C a_n + D}$ admit simple closed forms. The trick is to notice that by setting $\frac{p_n}{q_n}=a_n$, $p_0=a_0, q_0=1$ and $v_n=(p_n,q_n)^T$ we have $$v_{n+1} = \begin{pmatrix}A & B \\ C & D\end{pmatrix} v_n$$ hence $a_n$ is completely fixed by the powers of the involved matrix $M$. By the Hamilton-Cayley theorem the sequences $\{p_n\}_{n\geq 0}$, $\{q_n\}_{n\geq 0}$ have the same characteristic polynomial of $M$. If the eigenvalues of $M$ are distinct, it follows that $$a_n = \frac{a \lambda_1^n + b \lambda_2^n}{c \lambda_1^n + d \lambda_2^n}$$ where $\lambda_1,\lambda_2$ are the eigenvalues of $M$ and $a,b,c,d$ are suitable constants depending on the initial values. In your case the involved matrix is $$M = \begin{pmatrix}4 & 0 \\ 3 & 3\end{pmatrix}$$ which is lower triangular. It follows that $a_n = \frac{a4^n+b 3^n}{c 4^n+d 3^n}$ and by interpolating through the initial values we get $$a_n = \frac{3\cdot 4^n}{9\cdot 4^n-8\cdot 3^n} = \frac{1}{3}\left[1+\frac{1}{\frac{9}{8}\left(\frac{4}{3}\right)^n-1}\right]$$ so it is pretty obvious that $a_n\to\frac{1}{3}$ as $n\to +\infty$.

• I like your solution for the general problem and implemented if for random $A,B,C,D,a_1$. However, I find that that I can only determine $a,b,c,d$ to within an arbitrary factor, which is obvious when you look at the solution for $a_n$. More specifically, for the problem at hand I don't get the values $3,0,9,-8$, but a rather a set that is proportional to it. Any comments? – Cye Waldman Nov 18 '17 at 0:21
• @CyeWaldman: of course if the constants $A,B,C,D$ provide an explicit solution the constants $\lambda A,\lambda B,\lambda C,\lambda D$ (for $\lambda\neq 0$) provide exactly the same solution. In other terms $(A,B,C,D)$ has to be regarded as an element of $\mathbb{P}^3(\mathbb{C})$ rather than $\mathbb{C}^4$. – Jack D'Aurizio Nov 18 '17 at 0:37

If we write $a_n$ as $p_n/q_n$, we get:

$$a_{n + 1} = \frac{4(p_n/q_n)}{3(p_n/q_n)+3} = \frac{4p_n}{3p_n+3q_n} = \frac{p_{n+1}}{q_{n+1}}$$

In other words:

$$p_{n+1} = 4p_n \longrightarrow p_n = 4^{n-1}$$ $$q_{n+1} = 3p_n + 3q_n = 3\cdot 4^{n-1} +3 q_n$$

We can find $q_n$ with generating function $Q(x) = \sum_{n=1}^\infty q_nx^n$:

$$Q(x) = x + x\sum_{n=1}^\infty q_{n+1}x^n$$ $$Q(x) = x + 3x\sum_{n=1}^\infty (q_n + 4^{n-1})x^n$$ $$Q(x) = x + 3xQ(x) + 3x\sum_{n=1}^\infty 4^{n-1}x^n$$ $$(1 - 3x)Q(x) = x + 3x\frac{x}{1-4x}$$ $$Q(x) = \frac{x}{1-3x} + \frac{3x^2}{(1-3x)(1-4x)} = \frac{1}{4} +\frac{x}{1-3x} - \frac{1}{1-3x} + \frac{3}{4(1-4x)}$$

$$Q(x) = \frac{1}{4} + \sum_{n=1}^\infty3^{n-1}x^n - \sum_{n=1}^\infty3^{n}x^n + \frac{3}{4}\sum_{n=1}^\infty 4^nx^n$$

$$Q(x) = \frac{1}{4} + \sum_{n=1}^\infty(3^{n-1} - 3^n + \frac{3}{4}4^n)x^n = \sum_{n=1}^\infty q_nx^n$$

$$q_n = 3^{n-1} - 3^n + \frac{3}{4}4^n = \frac{1}{12}(9\cdot4^{n} - 8\cdot 3^{n})$$

Thus $a_n = \dfrac{3\cdot4^{n}}{9\cdot4^{n} - 8\cdot 3^{n}}$ giving limit $\dfrac{1}{3}$.