14
$\begingroup$

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.

  • 2
    If the first three terms are each $0$ or $1$ then $a_{n+12}=a_n$2012-07-13
  • 2
    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.2012-07-13
  • 0
    @ChrisDugale: right, i do the same thing; i think most of us do.2012-07-13
  • 0
    I just type the recursion into [Wolfram Alpha](http://www.wolframalpha.com/input/?i=a%5Bn%2B3%5D%3Da%5Bn%2B2%5D+a%5Bn%2B1%5D+-a%5Bn%5D). It tells you a lot about the sequence straight away, and sometimes gives a closed form. Sometimes it doesn't give one when it is possible to find one, but that's not so often.2012-07-13
  • 0
    If the first few terms are increasing, this is going to grow *really* fast.2012-07-13
  • 1
    @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.2012-07-13
  • 0
    You could also calculate some terms and ask [OEIS](http://oeis.org/)...2012-07-13
  • 1
    @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?2012-07-13
  • 0
    Thanks for all the input. I've been working with formal variables as initial conditions, so I can't really look for patterns in the terms. This discussion gives my an idea of some simple cases that might be manageable, though.2012-07-13
  • 0
    Maybe you are interested in this: [Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$](http://math.stackexchange.com/q/171597/19341)2012-07-16

1 Answers 1

13

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