Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

marked as duplicate by martini, Gerry Myerson, Pedro Tamaroff, Ross Millikan, William Sep 8 '12 at 17:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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 –  Golbez Sep 8 '12 at 9:24
How can this be achieved by matrix method?..any clue? –  Ravi Sep 8 '12 at 9:28
@PeterTaylor the initial values are different. How can th question be a duplicate –  Ravi Sep 8 '12 at 9:42
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 –  Martin Sleziak Sep 8 '12 at 9:47
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). –  Gerry Myerson Sep 8 '12 at 12:40

1 Answer 1

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

share|improve this answer

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