There is another function to calculate $T_n$?

Question

I was searching about Fibonacci numbers, and I found that Tribonacci numbers also exist given the following recurrence: $T_{n+3}= T_{n+2}+T_{n+1}+T{n}$ with $T_0=T_1=0,T_2=1$. Then I thought about what would be a function that would calculate the value $T_n$ and it would obviously be: $ F (n) = F(n-1) + F(n-2) - F(n-3) $, please correct me if it is not So. But, is there another way (function) to calculate this value without having to use recurrences?

Answer 1

Yes, you can solve the recurrence relation $F(n)=F(n-1)+F(n-2)+F(n-3)$ by solving its characteristic polynomial $x^3 = x^2 + x + 1$. This has a real solution $\alpha$ and two complex solutions $\beta, \gamma$, so the function will be given by $$F(n) = c_1 \alpha^n + c_2 \beta^n + c_3 \gamma^n$$ and we need to solve for $c_1, c_2, c_3$. We do this by substituting in the initial conditions:

\begin{align*} 0 = F(1) &= c_1 + c_2 + c_3 \\ 0 = F(2) &= c_1 \alpha + c_2 \beta + c_3 \gamma \\ 1 = F(3) &= c_1 \alpha^2 + c_2 \beta^2 + c_3 \gamma^2, \end{align*}

so we have to solve a system of $3$ equations and $3$ unknowns.

Answer 2

Suggestion:

You can use some matrix algebra

$$ \begin{pmatrix} F_{n+2}\\ F_{n+1}\\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1\\ 1 & 0 &0\\ 0 & 1& 0 \end{pmatrix}\begin{pmatrix} F_{n+1}\\ F_n\\ F_{n-1}\end{pmatrix} $$

Denote the matrix above by $A$ and then notice that if $\mathbf{V}_n:=[F_{n+2},F_{n+1},F_n]^\top$, then

$$ \mathbf{V}_n = A^n \mathbf{V}_1$$

Still, you have to do some work. Maybe see if you can find a spectral decomposition of $A$ (i.e. convenient canonical form) and which will allow you to compute things "faster".

Answer 3

Let $M$ be the matrix $\pmatrix{1 & 1 & 1\cr 1 & 0 & 0\cr 0 & 1 & 0\cr}$.
Then the third column of $M^n$ is $\pmatrix{T_{n+1}\cr T_{n}\cr T_{n-1}}$. You can compute $M^n$ very quickly using repeated squaring.

Answer 4

To do this numerically, it helps to remark that the cubic $x^3=x^2+x+1$ has three roots, only one of which has norm greater than $1$. Call that root $\alpha$. We note that, numerically, it is about $$\alpha \sim 1.83928675521416$$ It follows that, for large $n$, we have $T_n\sim C\alpha^n$ for some constant $C$. Numerically it looks like $C\sim .18280$.

Of course, this method is limited by the accuracy of our numerical estimates. There is a closed form for $\alpha$ if you prefer, but it isn't pretty:

$$\alpha = \frac 13\times \left(1 + (19 - \sqrt {33})^{1/3} + (19 + 3 \sqrt {33 }))^{1/3}\right)$$