How can I determine general formula of this sequence?

Question

I am trying to find general formula of the sequence $(x_n)$ defined by $$x_1=1, \quad x_{n+1}=\dfrac{7x_n + 5}{x_n + 3}, \quad \forall n>1.$$ I tried put $y_n = x_n + 3$, then $y_1=4$ and $$\quad y_{n+1}=\dfrac{7(y_n-3) + 5}{y_n }=7 - \dfrac{16}{y_n}, \quad \forall n>1.$$ From here, I can't solve it. How can I determine general formula of above sequence?

With Mathematica, I found $x_n = \dfrac{5\cdot 4^n-8}{4^n+8}$. I want to know a method to solve problem, than have a given formula.

Answer 1

Since the function being iterated is a projective-linear function, it follows that if you let $$ \begin{bmatrix} a_n \\ b_n \end{bmatrix} := \begin{bmatrix} 7 & 5 \\ 1 & 3 \end{bmatrix} ^{n-1} \begin{bmatrix} 1 \\ 1\end{bmatrix}$$ then $x_n = \frac{a_n}{b_n}$. Now, to find the powers of the matrix $\begin{bmatrix} 7 & 5 \\ 1 & 3 \end{bmatrix}$ all you need to do is to diagonalize it.

Answer 2

Here is a method that I read from a book. Yet I did not think deeply why it works in general.

---

If there exists real numbers $\alpha$, $\beta$ and $r$ such that

$$\frac{a_{n+1}-\beta}{a_{n+1}-\alpha}=r\cdot\frac{a_n-\beta}{a_n-\alpha}$$

for all $n\in\mathbb{N}$, then the sequence $\{b_n\}$, where $b_n=\frac{a_n-\beta}{a_n-\alpha}$, would be geometric and can be solved easily.

So our job is to find such $\alpha$, $\beta$ and $r$.

Substituting the recurring equation,

\begin{align} \frac{a_{n+1}-\beta}{a_{n+1}-\alpha}&=\frac{\frac{7a_n+5}{a_n+3}-\beta}{\frac{7a_n+5}{a_n+3}-\alpha} \\ &=\frac{7a_n+5-\beta(a_n+3)}{7a_n+5-\alpha(a_n+3)} \\ &=\frac{(7-\beta)a_n+(5-3\beta)}{(7-\alpha)a_n+(5-3\alpha)} \\ &=\frac{7-\beta}{7-\alpha}\cdot\frac{a_n-\left(-\frac{5-3\beta}{7-\beta}\right)}{a_n-\left(-\frac{5-3\alpha}{7-\alpha}\right)} \end{align}

Hence the trick should work if there is a solution for $\alpha=-\frac{5-3\alpha}{7-\alpha}$ and $\beta=-\frac{5-3\beta}{7-\beta}$ and $r=\frac{7-\beta}{7-\alpha}$.

Noting that $\alpha$ and $\beta$ are roots of $u=-\frac{5-3u}{7-u}$.

\begin{align} u&=-\frac{5-3u}{7-u} \\ u(7-u)&=-(5-3u) \\ u^2-4u-5&=0 \\ u&=-1\enspace\text{or}\enspace 5 \\ \end{align}

Take $(\alpha,\,\beta)=(-1,\,5)$. $r=\frac{7-5}{7-(-1)}=\frac{1}{4}$ follows.

$$b_1=\frac{a_1-\beta}{a_1-\alpha}=\frac{1-5}{1-(-1)}=-2$$

For all $n\in\mathbb{N}$,

$$b_n=r^{n-1}\cdot b_1=\left(\frac{1}{4}\right)^{n-1}(-2)=\frac{-8}{4^n}$$

Back substitute into $b_n=\frac{a_n-\beta}{a_n-\alpha}$.

\begin{align} \frac{-8}{4^n}&=\frac{a_n-5}{a_n-(-1)} \\ -8(a_n+1)&=4^n(a_n-5) \\ a_n&=\frac{5\cdot 4^n-8}{4^n+8} \end{align}

The same result as given by Mathematica.

Answer 3

The chracteristic equation of the given sequence is $$y=\dfrac{7y+5}{y+3} \Leftrightarrow y_1 = 5 \lor y_2 = -1.$$ Let us consider the sequence $$b_n = \dfrac{x_n-y_1}{x_n - y_2}=\dfrac{x_n-5}{x_n+1}.$$ We note that $$b_{n+1}=\dfrac{x_{n+1}-5}{x_{n+1}+1}=\dfrac{\dfrac{7x_n+5}{x_n+3}-5}{\dfrac{7x_n+5}{x_n+3} + 1}=\dfrac{2x_n-10}{8x_n + 8} = \frac{1}{4} \cdot \dfrac{x_n-5}{x_n +1 }=\frac{1}{4} b_n.$$ Therefore $(b_n)$ is a geometric progression, with ratio $\dfrac{1}{4}$ and the first term $$b_1 = \frac{x_1-5}{x_1+1}=\frac{1-5}{1+1}=\frac{-4}{2}=-2.$$ Therefore $$b_{n+1}=b_1 \cdot \left (\dfrac{1}{4}\right)^n= - 2 \cdot \left (\dfrac{1}{4}\right)^n,$$ or equaivalently, $$\dfrac{x_{n+1}-5}{x_{n+1}+1}=- 2 \cdot \left (\dfrac{1}{4}\right)^n \Leftrightarrow x_{n+1} = \frac{5\cdot 4^n - 2}{4^n +2}\Leftrightarrow x_n = \frac{5\cdot 4^n - 8}{4^n + 8}.$$