0
$\begingroup$

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}$?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}? $\endgroup$ – user132443 Mar 2 '14 at 10:22
  • $\begingroup$ 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. $\endgroup$ – LutzL Mar 2 '14 at 10:39
  • $\begingroup$ 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..). $\endgroup$ – user132443 Mar 2 '14 at 11:03
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Claude Leibovici Mar 2 '14 at 7:54
  • $\begingroup$ 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). $\endgroup$ – Robert Israel Mar 2 '14 at 7:57
  • $\begingroup$ Eveything becomes so obvious when properly explained ! Thanks a lot for teaching me so much. Cheers. $\endgroup$ – Claude Leibovici Mar 2 '14 at 7:59
  • $\begingroup$ @RobertIsrael How did you arrive at that polynomial? I'm curious to know $\endgroup$ – qwr Mar 2 '14 at 8:41
  • $\begingroup$ @qwr: It's the characteristic polynomial of the recurrence (or, if you prefer, of the matrix from LutzL's answer). $\endgroup$ – Robert Israel Mar 2 '14 at 9:02

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.