Generalised Fibonacci

Question

How to find the nth term of the recurrence in $\log n$ time.

$$ \begin{array}{rcl} F[n]&=&F[n-1]+F[n-3]\\ F[2]&=&1\\ F[3]&=&2\\ F[4]&=&3\\ F[5]&=&4 \end{array} $$

I could not create the required matrix to exponentiate.

Answer 1

For $F[n]=F[n-1]+F[n-3]$, $$ \begin{pmatrix}1&0&1\\1&0&0\\0&1&0\end{pmatrix} \begin{pmatrix}F[n-1]\\F[n-2]\\F[n-3]\end{pmatrix} = \begin{pmatrix}F[n]\\F[n-1]\\F[n-2]\end{pmatrix}. $$ Is this the thing you want?