Tribonacci Numbers by Matrix Exponentiation¶

The Tribonacci sequence used here is

$$ T_0=0,\quad T_1=0,\quad T_2=1,\qquad T_{n+3}=T_{n+2}+T_{n+1}+T_n. $$

A companion matrix turns this recurrence into repeated linear algebra, which makes fast exponentiation available.

Build the transition matrix by pattern matching¶

The first row sums the three current state entries. The subdiagonal shifts the older values down one position:

$$ A= \begin{pmatrix} 1&1&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}. $$

The generator describes those two structural patterns rather than listing nine unrelated entries.

def m : Integer := 3

def A : Matrix Integer :=
  generateTensor
    (\match as list integer with
      | [#1, _] -> 1
      | [$x, #(x - 1)] -> 1
      | _ -> 0)
    [m, m]

$\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{pmatrix}$

Initial state¶

The vector $B=(1,0,0)^\mathsf T$ stores $(T_2,T_1,T_0)^\mathsf T$.

def B : Vector Integer :=
  generateTensor
    (\[x] -> if x = 1 then 1 else 0)
    [m]

def tribonacciState (n : Integer) : Vector Integer :=
  MV.* (M.power A n) B

$\begin{pmatrix} 1 \\ 0 \\ 0\\ \end{pmatrix}$

Advance the recurrence¶

For every $n\ge0$,

$$ A^nB=(T_{n+2},T_{n+1},T_n)^\mathsf T. $$

The first few full states make both the recurrence and the indexing convention visible.

tribonacciState 1

$\begin{pmatrix} 1 \\ 1 \\ 0\\ \end{pmatrix}$

tribonacciState 3

$\begin{pmatrix} 4 \\ 2 \\ 1\\ \end{pmatrix}$

tribonacciState 5

$\begin{pmatrix} 13 \\ 7 \\ 4\\ \end{pmatrix}$

Jump directly to a large index¶

Matrix exponentiation uses repeated squaring, so computing $A^{100}B$ does not require one hundred explicit recurrence steps.

tribonacciState 100

$\begin{pmatrix} 180396380815100901214157639 \\ 98079530178586034536500564 \\ 53324762928098149064722658\\ \end{pmatrix}$

Takeaway¶

Pattern matching gives a compact structural definition of the companion matrix, while tensor contraction performs the matrix-vector product. The first component of the final vector is $T_{102}$ under the stated indexing convention.