Tetranacci Numbers in Log(n)

Question

I have stumbled upon a problem, which requires me to calculate the nth Tetranacci Number in O(log n).

I have seen several solutions for doing this for Fibonacci Numbers

I was looking to follow a similar procedure (Matrix Multiplication/Fast Doubling) to achieve this, but I am not sure how to do it exactly (take a 4 by 4 matrix and 1 by 4 in a similar fashion doesn't seem to work). With dynamic programming/general loops/any other basic idea, I am not able to achieve sub-linear runtime. Any help appreciated!

Answer 1

Matrix multiplication of course works. Here's how to derive the matrix.

What we want is to find the entries that make the equation

[a b c d] [T(n-1)]   [T(n)  ]
[e f g h] [T(n-2)]   [T(n-1)]
[i j k l] [T(n-3)] = [T(n-2)]
[m n o p] [T(n-4)]   [T(n-3)]

true for all n. Expand.

a T(n-1) + b T(n-2) + c T(n-3) + d T(n-4) = T(n)
e T(n-1) + f T(n-2) + g T(n-3) + h T(n-4) = T(n-1)
i T(n-1) + j T(n-2) + k T(n-3) + l T(n-4) = T(n-2)
m T(n-1) + n T(n-2) + o T(n-3) + p T(n-4) = T(n-3)

The obvious settings here are a = b = c = d = 1 (using the recurrence) and e = j = o = 1 and f = g = h = i = k = l = m = n = p = 0 (basic algebra).

The initial vector is

[T(3)]   [1]
[T(2)]   [0]
[T(1)] = [0]
[T(0)]   [0]

by definition.