15
$\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.

$\endgroup$
10
  • 2
    $\begingroup$ If the first three terms are each $0$ or $1$ then $a_{n+12}=a_n$ $\endgroup$
    – Henry
    Jul 13, 2012 at 4:05
  • 2
    $\begingroup$ 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. $\endgroup$
    – RougeSegwayUser
    Jul 13, 2012 at 4:05
  • $\begingroup$ @ChrisDugale: right, i do the same thing; i think most of us do. $\endgroup$
    – Aang
    Jul 13, 2012 at 4:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ragib Zaman
    Jul 13, 2012 at 5:17
  • 1
    $\begingroup$ @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? $\endgroup$
    – Did
    Jul 13, 2012 at 9:19

1 Answer 1

Reset to default
14
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .