# Generalised Fibonacci

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.

-
It's worth noting there is a closed form solution to this equation, it can easily be found using this. –  Darksonn Aug 9 at 12:44

## 1 Answer

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?

-
+1, this fits the bill. And also leads to a $\log n$ complexity calculation, as the powers of this matrix can be calculated fast using square-and-multiply. –  Jyrki Lahtonen Aug 9 at 12:14
thanks... just the thing i was looking for. –  Raj Shah Aug 9 at 12:15
@The Great Seo can you explain the underlying logic... how did you get to dis? –  Raj Shah Aug 9 at 12:52
@RajShah I cannot describe my 'feeling' explicitly, but here is my way: I think you already know that the form has to be ($n\times n$ matrix)($1\cdot n$ matrix)=($1\cdot n$ matrix), while ($1\cdot n$ matrix) is formed by $F[-]$s, and ($n\times n$ matrix) describes the relation between $F[-]$s. Since we have $F[n]=1\cdot F[n-1]+0\cdot F[n-2]+1\cdot F[n-3]$ as the relation, $n=3$(=# of terms in LHS). –  The Great Seo Aug 9 at 13:04