2
$\begingroup$

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?

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

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

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

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.