Tribonacci generating matrix

I know that $$T(0) = 0$$ and $$T(1) = T(2) = 1$$. For $$n \ge 3$$,

$$T(n)=T(n-1)+T(n-2)+T(n-3)$$

Now I find that

$$\begin{bmatrix}T(n+1)\\T(n)\\T(n-1)\end{bmatrix} = \begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}\cdot\begin{bmatrix}T(n)\\T(n-1)\\T(n-2)\end{bmatrix} = \cdots=\begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}^n\cdot\begin{bmatrix}1\\1\\0\end{bmatrix}$$

How do I find now that $$\begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}^n = \begin{bmatrix} T(n+1)&T(n)+T(n-1)&T(n)\\T(n)&T(n-1) + T(n-2)&T(n-1)\\T(n-1)&T(n-2)+T(n-3)&T(n-2)\end{bmatrix}$$

Do I need to guess? Or there is a way to do it?

• The power of the matrix should contain integers, not $T$'s. – Rodrigo de Azevedo Mar 15 at 16:56
• @RodrigodeAzevedo I don't understand, I want to calculate $(n+1)th$ tribonacci number by powering matrix and I guess that's the answer. – Nerwena Mar 15 at 17:01
• Do you know how to diagonalize a matrix? – user170231 Mar 15 at 17:01
• Start with $n=2$ and you will see. – Rodrigo de Azevedo Mar 15 at 17:02
• Do you have to diagonalize? You have a companion matrix. – Rodrigo de Azevedo Mar 15 at 17:02

1 Answer

One option is surely to get your transfermatrix, say $$\mathbb M$$, (that one with zeros and ones) as solution of one step of iteration.

So for instance $$[T_0, T_1, T_2] \cdot \mathbb M = [T_1,T_2,T_3] \Rightarrow \text{ find } \mathbb M$$ . Now this simple ansatz does not yet help, because we cannot apply matrix-inversion on the one-row vector on the lhs.

But instead to have only a one-row vector on the lhs, we can construct square matrices $$\mathbb T_0$$,$$\mathbb T_1$$ to attempt $$\mathbb T_0 \cdot \mathbb M = \mathbb T_1 \Rightarrow \mathbb M = \mathbb T_0^{-1} \cdot \mathbb T_1$$ : $$\begin{array}{ccc} & & \mathbb M \\ & * & ========\\ \left[\begin{array}{} T_0&T_1&T_2 \\T_1&T_2&T_3 \\T_2&T_3&T_4 \end{array}\right] & = & \left[\begin{array}{} T_1&T_2&T_3 \\T_2&T_3&T_4 \\T_3&T_4&T_5 \end{array}\right] \\ \end{array}$$ Then $$\mathbb T_0 \cdot \mathbb M^n = \mathbb T_n$$ by construction.

Note: It would have been better to use small letters for scalar values and capital letters for the matrices, but well: I just used the "mathbb"-attribute for distinction

• Ah, @ParamanandSingh -thanks for the notification! I even wanted to expand/detail my complimentary comments, but was distracted. Good to be reminded :-) – Gottfried Helms Apr 7 at 18:23