<s>[INST] Can we get the closed-form solution of $x_{n+1} = \frac{1+5 x_n}{1+x_n}$? When reading a textbook I encounter a sequence, the closed-form solution of which, claims the author, can be derived. The sequence reads:
\begin{gather*}
x_{n+1} = \frac{1+5 x_n}{1+x_n}
\end{gather*}
and $x_1=1$. The author gives without proof that
$$
x_n = \frac{4+2\sqrt{5}-(\sqrt{5}-1)c^{2-t}}{2+(\sqrt{5}+3)c^{2-t}}
$$
where $c = \frac{1}{2}(7+3\sqrt{5})$.
It seems that we can formulates the problem in a more general framework, say a sequence
$$
y_{n+1} = a+\frac{b}{y_n+c}
$$
I can't see how this kind of sequence can be solved explicitly. Can anyone give a hint on the problem?
 [/INST] Hint. A standard route is as follows. One may 'linearize' the given recurrence in a 'matrix frame' by writing
$$
\begin{align}
x_{n+1}&=\underbrace{\left(\begin{matrix} 1 & 5 \\ 1 & 1 \end{matrix}\right)}_{\large A}\cdot x_{n}
\end{align}
$$ giving directly
$$
x_n=A^n \cdot x_1
$$ then, by diagonalizing  the matrix $A$,
$$
\begin{align}
A=P \cdot J \cdot P^{-1} =\left(\begin{matrix} -\sqrt{5} & \sqrt{5} \\ 1 & 1 \end{matrix}\right)\left(\begin{matrix} 1-\sqrt{5} & 0 \\ 0 & 1+\sqrt{5} \end{matrix}\right)\left(\begin{matrix} -\frac{\sqrt{5}}{10} & \frac12 \\ \frac{\sqrt{5}}{10} & \frac12 \end{matrix}\right)
\end{align}
$$ one easily gets
$$
x_n=P \cdot J^n \cdot P^{-1} \cdot x_1
$$ that is
$$
x_n=\left(\begin{matrix} -\sqrt{5} & \sqrt{5} \\ 1 & 1 \end{matrix}\right)\left(\begin{matrix} (1-\sqrt{5})^n & 0 \\ 0 & (1+\sqrt{5})^n \end{matrix}\right)\left(\begin{matrix} -\frac{\sqrt{5}}{10} & \frac12 \\ \frac{\sqrt{5}}{10} & \frac12 \end{matrix}\right) \cdot x_1
$$ obtaining a closed form of $x_n$.
</s>