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?

  • 1
    $\begingroup$ Use this as an example. $\endgroup$
    – rtybase
    Apr 4, 2021 at 17:15

2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.