MHB Solution to Sequence Challenge $a_n$

[Albert1]

$a_1=2 ,$ and

$a_{n+1}=\dfrac{a_n+4}{2a_n+3},\,\, n\in N$

find :$a_n$

 

[Nono713]

Spoiler

First note that this sequence lies in $\mathbb{Q}$. Thus we can write $a_n = u_n / v_n = (u_n, v_n)$ as a two-dimensional vector for integers $u_n, v_n$. We now get:

$$a_{n + 1} = \frac{u_{n + 1}}{v_{n + 1}} = \frac{a_n + 4}{2 a_n + 3} = \frac{\frac{u_n}{v_n} + 4}{2 \frac{u_n}{v_n} + 3} = \frac{u_n + 4 v_n}{2 u_n + 3 v_n}$$

Hence we can express the recurrence as a linear transformation of the vector $(u_n, v_n)$ given by the matrix:

$$A = \left [ \begin{matrix} 1 &4 \\ 2 &3 \end{matrix} \right ]$$

Such that:

$$\left [ \begin{matrix} u_{n + 1} \\ v_{n + 1} \end{matrix} \right ] = A \left [ \begin{matrix} u_n \\ v_n \end{matrix} \right ]$$

And, more importantly for now:

$$\left[ \begin{matrix} u_n \\ v_n \end{matrix} \right ] = A^n \left [ \begin{matrix} u_1 \\ v_1 \end{matrix} \right ] = A^n \left [ \begin{matrix} 2 \\ 1 \end{matrix} \right ]$$

Since $a_1 = 2 = 2/1$. This matrix $A$ has eigenvalues $5$ and $-1$, with respective eigenvectors $(1, 1)$ and $(-2, 1)$. Those represent the steady states of the system, i.e. $1$ and $-2$. So we can diagonalize it as follows:

$$A = \left [ \begin{matrix} 1 &-2 \\ 1 &1 \end{matrix} \right ] \left [ \begin{matrix} 5 &0 \\ 0 &-1 \end{matrix} \right ] \left [ \begin{matrix} 1 &-2 \\ 1 &1 \end{matrix} \right ]^{-1} = \frac{1}{3} \left [ \begin{matrix} 1 &-2 \\ 1 &1 \end{matrix} \right ] \left [ \begin{matrix} 5 &0 \\ 0 &-1 \end{matrix} \right ] \left [ \begin{matrix} 1 &2 \\ -1 &1 \end{matrix} \right ]$$

And so by diagonalization, we have:

$$A^n = \frac{1}{3^n} \left [ \begin{matrix} 1 &-2 \\ 1 &1 \end{matrix} \right ] \left [ \begin{matrix} 5^n &0 \\ 0 &(-1)^n \end{matrix} \right ] \left [ \begin{matrix} 1 &2 \\ -1 &1 \end{matrix} \right ] = \frac{1}{3^n} \left [ \begin{matrix} 5^n + 2(-1)^n &2 \cdot 5^n - 2 (-1)^n \\ 5^n - (-1)^n &2 \cdot 5^n + (-1)^n \end{matrix} \right ]$$

And so:

$$\left[ \begin{matrix} u_n \\ v_n \end{matrix} \right ] = A^n \left [ \begin{matrix} 2 \\ 1 \end{matrix} \right ] = \frac{1}{3^n} \left [ \begin{matrix} 4 \cdot 5^n + 2 (-1)^n \\ 4 \cdot 5^n - (-1)^n \end{matrix} \right ]$$

We conclude (note the factor of $3^{-n}$ is present in both $u_n$ and $v_n$ and so cancels out):

$$a_n = \frac{u_n}{v_n} = \frac{4 \cdot 5^n + 2 (-1)^n}{4 \cdot 5^n - (-1)^n}$$​

 

[Albert1]

according to your answer :
$a_1=\dfrac {18}{21}\neq 2$

 

[Euge]

Spoiler

Let $\text{GL}_2(\Bbb Z)$ act on $\hat{\Bbb C}$ by setting $A\cdot z := \frac{az + b}{cz + d}$, for

$$ A = \begin{pmatrix}a & b\\c & d\end{pmatrix}\in \text{GL}_2(\Bbb Z)$$

and $z\in \hat{\Bbb C}$. Let $A = \begin{pmatrix}1 & 4\\2 & 3\end{pmatrix}$. Then $a_{n+1} = A\cdot a_n$ for all $n \ge 1$. Thus $a_{n+1} = A^n\cdot a_1 = A^n \cdot 2$ for all $n \ge 1$. By diagonalization,

$$A = \begin{pmatrix}-2 & 1\\1 & 1\end{pmatrix} \begin{pmatrix}-1 & 0\\0 & 5\end{pmatrix} \begin{pmatrix}-\frac{1}{3} & \frac{1}{3}\\\frac{1}{3} & \frac{2}{3}\end{pmatrix}.$$

Thus

$$A^n = \begin{pmatrix}-2 & 1\\1 & 1\end{pmatrix} \begin{pmatrix}(-1)^n & 0\\0 & 5^n \end{pmatrix} \begin{pmatrix}-\frac{1}{3} & \frac{1}{3}\\\frac{1}{3} & \frac{2}{3}\end{pmatrix} = \begin{pmatrix} \frac{2(-1)^n + 5^n}{3} & \frac{2\cdot 5^n - 2(-1)^n}{3}\\\frac{5^n - (-1)^n}{3} & \frac{2\cdot 5^n + (-1)^n}{3}\end{pmatrix},$$

and

$$a_{n+1} = A^n \cdot 2 = \dfrac{2\frac{2(-1)^n + 5^n}{3} + \frac{2\cdot 5^n - 2(-1)^n}{3}}{2\frac{5^n - (-1)^n}{3} + \frac{2\cdot 5^n + (-1)^n}{3}} = \frac{4\cdot 5^n + 2(-1)^n}{4\cdot 5^n + (-1)^{n+1}},$$

for all $n \ge 1$. When $n = 0$, $\frac{4\cdot 5^n + 2(-1)^n}{4\cdot 5^n + (-1)^{n+1}} = \frac{4 + 2}{4 - 1} = \frac{6}{3} = 2 = a_1$. Hence,

$$a_n = \frac{4\cdot 5^{n-1} + 2(-1)^{n-1}}{4\cdot 5^{n-1} + (-1)^n}$$

for all $n\ge 1$.

 

[topsquark]

Thanks you two. I wasn't aware that there was a general method for attacking such a problem.

-Dan

 

[Nono713]

according to your answer :
$a_1=\dfrac {18}{21}\neq 2$

Off by one error... if you replace $n$ by $n - 1$ it works properly.. iterating the recurrence one time will give $a_2$, but I forgot the sequence started at $n = 1$, not $n = 0$.. will fix later.

 

[Albert1]

$a_1=2 ,$ and

$a_{n+1}=\dfrac{a_n+4}{2a_n+3},\,\, n\in N$

find :$a_n$

Spoiler

let :
$x=\dfrac{x+4}{2x+3}---(1)$
the solutions of (1) $x=-2,1$
$\therefore \dfrac {a_{n+1}+2}{a_{n+1}-1}=-5(\dfrac {a_{n}+2}{a_{n}-1})=----=(-5)^{n}(\dfrac {a_1+2}{a_1-1})=(-5)^{n}\times 4$
and we get :
$a_n=\dfrac{4(-5)^{n-1}+2}{4(-5)^{n-1}-1}$