Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 1

up vote 4 down vote accepted

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?

share|improve this answer
1  
+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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.