Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
If the first three terms are each $0$ or $1$ then $a_{n+12}=a_n$ – Henry Jul 13 '12 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. – Chris Dugale Jul 13 '12 at 4:05
@ChrisDugale: right, i do the same thing; i think most of us do. – Aang Jul 13 '12 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. – Ragib Zaman Jul 13 '12 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 '12 at 9:19
up vote 13 down vote accepted

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)}. $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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