How to solve the nonlinear recurrence relation $a_{n+1} = \frac{1-a_n}{3+a_n}$ I know how to solve linear recurrence relations and I'm familiar with generating functions, but I don't know any methods to solve some non-linear recurrence relations.
I stumbled upon the following recurrence relation that I would like to know how to solve. Consider the sequence defined by
$$
a_0 = 0 \quad\text{and}\quad a_{n+1} = \frac{1-a_n}{3+a_n}\quad\text{for }n\geq 0.
$$
I used RSolve in Mathematica to see that this recurrence relation is solved by
$$
a_n = \frac{\left(\sqrt{5}+1\right)^n-\left(1-\sqrt{5}\right)^n}{\left(\sqrt{5}-2\right) \left(1-\sqrt{5}\right)^n+\left(\sqrt{5}+2\right) \left(\sqrt{5}+1\right)^n}.
$$
But how on earth would I be able to solve something like this on my own? Where does an answer like this come from?
 A: Here is one way to solve this using linear algebra.
Step 1, Homogenize the original recurrence relation $a_{n+1}=\frac{1-a_n}{3+a_n}$ by setting $a_n=\frac{X_n}{Y_n}$ and thus the recurrence relation becomes
$$\frac{X_{n+1}}{Y_{n+1}}=\frac{Y_n-X_n}{3Y_n+X_n}.$$
Step 2, Since we only care about the quotient $X_n/Y_n$, we can assume that $X_{n+1}=Y_n-X_n$ and $Y_{n+1}=3Y_n+X_n$. If we consider the vector $$v_n=\begin{bmatrix}X_n\\ Y_n \end{bmatrix},$$
the recurrence relation can be written as
$$v_{n+1}=Av_n, \qquad \textrm{ with } A=\begin{bmatrix}-1& 1\\ 3&1 \end{bmatrix}.$$
Thus $$v_n=A^nv_0,$$
with $v_0=[0,1]^T.$
Step 3, Diagonalize matrix $A$ and compute $A^n$. This is standard.
Step 4, Compute $X_n, Y_n$ and thus $a_n$.
Edit: I just find out this is the method used in one answer of a similar question How to solve the recurrence relation $a_{1}=2, a_{n}=\frac{a_{n-1}+2}{2 a_{n-1}+1}(n \geq 2)$ with generating functions?
A: In my answer to this question, I detailed the steps for solving a first-order rational difference equation such as
$${ a_{n+1} = \frac{ma_n + x}{a_n + y} }$$
For your case $m=-1$, $x=1$, $y=3$ makes the problem quite simple.
