# Solving a Nonlinear Recursion

In the course of some research computations I have been doing, I run up against a recursion $$a_{n+3} = a_{n+2}a_{n+1} - a_n$$

I've tried to find out if it's possible to solve recursions of this form, but can't find much since it's nonlinear. Does anyone know of methods that might be applicable; or failing that, if there are any assumptions on the initial conditions which might make it solvable?

Hope this is clear; I don't have any background in number theory or discrete math. Thanks.

• If the first three terms are each $0$ or $1$ then $a_{n+12}=a_n$ Jul 13, 2012 at 4:05
• Personaly, when I run into things like this, I do the following. Compute a few terms from $a_0$. By a few terms I mean, perhaps, more than 25. Then, Look at what you've produced, and see if you can find a pattern. If you can find a pattern, then you've gotten lucky, and may be able to do soemthing with induction. Jul 13, 2012 at 4:05
• @ChrisDugale: right, i do the same thing; i think most of us do.
– Aang
Jul 13, 2012 at 4:59
• @AlexBecker Indeed, this grows slower than $b_{n+3} = b_{n+2} b_{n+1}$ (simply omitting the subtracted term) and that has solutions of the form $b_n = \exp ( c_1 F_n + c_2 L_n)$ where $F_n$ and $L_n$ are the Fibonacci and Lucas numbers. Jul 13, 2012 at 5:17
• @Henry: Wow! (With period 12 when at least two ones in the starting word $a_0a_1a_2$, period 6 when exactly one one, and period 1 when no one.) Why is that so?
– Did
Jul 13, 2012 at 9:19

Let $F_1,F_2,\dots$ be a Fibonacci-like sequence, such that $F_{n}=F_{n-1} + F_{n-2}$, and let $$a_{n} = e^{F_{n}} + e^{-F_{n}} = 2\cosh F_n.$$ Then $$\begin{eqnarray} a_{n-1}a_{n-2} &=& \left(e^{F_{n-1}} + e^{-F_{n-1}}\right) \left(e^{F_{n-2}} + e^{-F_{n-2}}\right) \\ &=& e^{F_{n-1} + F_{n-2}} + e^{F_{n-1} - F_{n-2}} + e^{-F_{n-1} + F_{n-2}} + e^{-F_{n-1} - F_{n-2}} \\ &=& e^{F_{n}} + e^{F_{n-3}} + e^{-F_{n-3}} + e^{-F_{n}} \\ &=& a_{n} + a_{n-3}, \end{eqnarray}$$ which is exactly your recursion. This family of solutions, parametrized by $(F_1, F_2)$, only covers part of the full range of initial conditions $(a_1, a_2, a_3)$. In particular, it will cover those cases where $$a_3 = \frac{1}{2} a_1 a_2 \pm \frac{1}{2}\sqrt{\left(a_1^2-4\right)\left(a_2^2-4\right)}.$$