# 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?

• Use this as an example. Apr 4, 2021 at 17:15

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?

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.