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

| cite | improve this answer | |
$\endgroup$

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.