Possible Duplicate:
Fibonacci, tribonacci and other similar sequences

Suppose my Tribonacci series is like this: \begin{equation} T(n) = T(n-1) + T(n-2) +T(n-3) \end{equation} with initial values $T(0) = 1, T(1) = 2$ and $T(2) = 3$, then how do I find $T(10000)$?

  • $\begingroup$ Solving equation $x^3=x^2+x+1$, when $x_1,x_2,x_3$ are roots of the equation, we have $T(n)=a_1 x_1^n+a_2 x_2 ^n+a_3 x_3^n$, when we have $T(1),T(2),T(3)$ we can get $a_1,a_2,a_3$ and done $\endgroup$ – Golbez Sep 8 '12 at 9:24
  • $\begingroup$ How can this be achieved by matrix method?..any clue? $\endgroup$ – Ravi Sep 8 '12 at 9:28
  • $\begingroup$ @PeterTaylor the initial values are different. How can th question be a duplicate $\endgroup$ – Ravi Sep 8 '12 at 9:42
  • $\begingroup$ I think that the usual matrix method for Fibonacci numbers can be adapted to any linear recurrence. You just need to compute $n$-th power of some matrix. Also this post at SO might be useful for you: nth fibonacci number in sublinear time $\endgroup$ – Martin Sleziak Sep 8 '12 at 9:47
  • $\begingroup$ It's a duplicate in the sense that if you take the trouble to understand what's at that other question you'll have no trouble answering yours (and if you do have trouble, you can always try again). $\endgroup$ – Gerry Myerson Sep 8 '12 at 12:40

There is no clever method. Associated characteristic equation $$ x^3-x^2-x-1=0 $$ got a real solutions $\varphi$ and two conjuguate complex solutions $\psi,\overline{\psi}$. Using an online cubic equation solver yields : $$ \varphi = 1.8392867552141612 $$ $$ \psi = -0.41964337760708065 + 0.6062907292071992 i$$ If you are looking for rational expression then take a look at this.

The Tribonacci general term is thus $$ T(n) = a \varphi^n + b \psi^n + c\left(\overline{\psi}\right)^n $$

Your initial conditions gives you the values for $a,b,c$. Then $$ T(10000) = a \varphi^{10000} + b \psi^{10000} + c\left(\overline{\psi}\right)^{100000} $$


Not the answer you're looking for? Browse other questions tagged or ask your own question.