# Calculate nth element of fibonacci-like sequence

Given the sequence: $a_1 = 2$, $a_2 = 5$, $a_3 = 6$, $a_4 = a_1+a_2+a_3$, $a_5 = a_2+a_3+a_4$, ... , $a_n = a_{n-3}+a_{n-2}+a_{n-1}$

Can I quickly determine $a_n$, without calculating all previous $a_i$ (that's because $n$ can be very large, even $2*10^{15}$?

You may also go the way of matrix iterations. The given recursion requires a "back memory" of three elements, $a_{n+1}$ is computed from $a_n,\,a_{n-1},\,a_{n-2}$, and $a_{n-2}$ is then dropped from the memory. Thus the iteration matrix will have size $3\times 3$ as follows $$\begin{bmatrix} a_{n+1}\\a_n\\a_{n-1} \end{bmatrix} = \begin{bmatrix} 1&1&1\\ 1&0&0\\ 0&1&0 \end{bmatrix} \cdot \begin{bmatrix} a_{n}\\a_{n-1}\\a_{n-2} \end{bmatrix} = \begin{bmatrix} 1&1&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}^{n-1} \cdot \begin{bmatrix} a_{2}\\a_{1}\\a_{0} \end{bmatrix}.$$ The first row represents the iteration equation, the second row copies $a_n$ from first to second place, likewise the third for $a_{n-1}$ from second to third place.

One can employ halving-and-squaring to rapidly compute the necessary matrix power for large $n$ and thus also the sequence elements.

$A^n$ is computed for even powers $n=2m$ as $(A^m)^2$ and for odd $n=2m+1$ as $(A^m)^2\cdot A$, reducing the number of matrix multiplications from $n-1$ for the naive method to less than $2\log_2 n$.

• How did you get the 1-0 matrix? How will this equation look, if we have, for example, 4 starting numbers and a_n = a_{n-4}+a_{n-3}+a_{n-2}+a_{n-1}? – user132443 Mar 2 '14 at 10:22
• The first line is the recursion equation, following matrix-vector multiplication rules, the other lines shift the vector components by one place. See also "companion matrix" on wikipedia. For your extended example, you would need a $4\times 4$ matrix. The eigenvalues of the matrix are the roots t of the characteristic polynomial in the other answer. – Lutz Lehmann Mar 2 '14 at 10:39
• I see it's too hard math for me. I'm sure there's easier way - I get that problem from teacher, and on our lessons we didn't learn matrixes and roots of the polynomial (To be honest, I don't even know what is it..). – user132443 Mar 2 '14 at 11:03

$n = 2 \times 10^{15}$ may be a bit much: your $a_n$ would have more than $5 \times 10^{14}$ decimal digits. Where would you put them if you could compute them?

For $n>3$, $a_n$ is the closest integer to $\dfrac{4+3t-t^2}{3+2t+t^2} t^{1+n}$ where $t = \dfrac{1}{3} \left(19 + 3 \sqrt{33}\right)^{1/3} + \dfrac{4}{3} \left(19 + 3 \sqrt{33}\right)^{-1/3} + \dfrac{1}{3}$ is the real root of the polynomial $x^3 - x^2 - x - 1$, approximately $1.839286755$.

• May I ask how you arrived to this interesting formula ? Since two of the roots of the characteristic polynomial are complex, I arrived to somethinh awful (which works). – Claude Leibovici Mar 2 '14 at 7:54
• The other two roots have absolute value less than $1$, so their contributions are small for large $n$ (in this case $n>3$ turns out to be enough). – Robert Israel Mar 2 '14 at 7:57
• Eveything becomes so obvious when properly explained ! Thanks a lot for teaching me so much. Cheers. – Claude Leibovici Mar 2 '14 at 7:59
• @RobertIsrael How did you arrive at that polynomial? I'm curious to know – qwr Mar 2 '14 at 8:41
• @qwr: It's the characteristic polynomial of the recurrence (or, if you prefer, of the matrix from LutzL's answer). – Robert Israel Mar 2 '14 at 9:02