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?
Best Answer
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?