How to find Nth term of any linear recurrence relation in O( logN )

 5 min read 

Motivation: Given a sequence with a recurrence relation. Find is the Nth term of the sequence.

Example: Fibonacci sequence

First, let's analyze how we can find the Nth term of the Fibonacci sequence in O(logN) time complexity after that we will see how we can find the Nth term of any linear recurrence relation.

As we all know this is the Fibonacci sequence:

and the recurrence relation of the Fibonacci sequence is:

where we already know what is F(0) and F(1).

So let's write F(2): 

Now let's write F(3):

here we can see that for computing F(3) we need to know what is the value of F(2) but we only know F(0) and F(1). 

So, let's rewrite F(3) in term of F(1) and F(0): 

Now let's write F(4):

here again, we can see that for computing F(4) we need to know what is the value of F(3) and F(2).

So, let's again rewrite F(4) in term of F(1) and F(0): 

Now let's write F(5) in terms of F(1) and F(0) :

So, From the above values of F(2), F(3), F(4), and F(5) we analyze that any term of the Fibonacci 

sequence can be written in the term of F(1) and F(0) i.e

Now let's try to write the recurrence relation in the form of the matrix.

                       

First, write the right part of the above recurrence relation in the form of a matrix.

So for that, we need a 2 X 1 size matrix i.e

But our goal is to find F(N) using F(N-1) and F(N-2) for that we also need to make the left part of the recurrence relation in the form of a matrix. But what will be the size of that matrix? 

Let's assume the size of that matrix also a 2 X 1 i.e 
Now putting the values of M1 and M2.

But we can see that both matrices are not equal, so we need to do something so that left and right parts become equal. 

For this, if somehow the first row of the matrix becomes equal to F(N-1) + F(N-2) then we can say that the first row of both the matrix is equal because F(N-1) + F(N-2) = F(N).

So, our task is to make the first row of matrix M2 equal to F(N-1) + F(N-2).

But alone with M2, we can't do this. So, we need one more matrix and assume we will cross multiply that new matrix with M2 i.e 

But what will be the size of this new matrix?

As we all know for cross multiplication of two matrices the number of columns in the left matrix must be equal to the number of rows in the right matrix. 

It means C = 2. 

And we also know after cross multiplication of two matrices of size  R1 X C1 and R2 X C2 the size of the resultant matrix will be equal to R1 X C2. 

It means R = 2 because our resultant matrix is of size 2 X 1. 

So the size of the new matrix is 2 X 2.

Now, our new task is to find the value of this new matrix.

After cross multiplication 

Since we want first row equal to F(N-1) + F(N-2) it means A and B must be equal to 1 i.e 

Now for finding the values of C and D first, we have to know what is the value in the second row of matrix M1.

Now if we observer matrix M1 and M2 

                                    

M2 has N-1th term and N-2th term and M1 have only Nth term. So by similarity, Can we say that the other term of the matrix M1 can be N-1th term? i.e 

Yes, because now both the matrices have adjacent terms of the Fibonacci sequence. 

So now we can say that we want F(N-1) in the second row of the resultant matrix.

For that, we can say that C must be equal to 1 and D equal to 0.

So the values of the new matrix are: 

Now we can say that this recurrence relation F(N) = F(N-1) + F(N-2) can be written like this in the form of matrices. 

Let's start again but using the above matrices relation.

So let's write the matrix relation for F(2):  

the value of F(2) is the value in the first row of the resultant matrix. 

Now let's write F(3):

Here again, for computing F(3), we need F(2) but we have only know F(0) and F(1). So let's rewrite it in terms of F(1) and F(0).

Now let's write F(4):

Again we need to rewrite it in F(1) and F(0).

Now let's write F(5):

Now if we observe, to find F(2) we need one power of that new matrix.

For F(3) we need two power of that new matrix.

For F(4) we need three power of that new matrix.

For F(5) we need four power of that new matrix.

So, If we generalize it. For F(N) we need N-1 power of that new matrix i.e 

Now the obvious complexity to find Nth term using the above formulae is O(N). 

This complexity is good when N < 10^6.

So how we can find the Nth term when N = 10^16? 

To find A^N we can use fast exponentiation with repeating square ( Link: https://www.youtube.com/watch?v=P4FiM5moimE&t= ) with the complexity of O(logN).

If we use the same technique for the matrix then we can find Nth term of the Fibonacci sequence in O(logN) time complexity. 

Original Complexity: O( TIme for multiplication of two matrices X logN ) 

Try to solve these problems: 

1. https://www.codechef.com/problems/CEXE08

2. https://www.spoj.com/problems/ASUMHARD/

3. https://www.spoj.com/problems/SUMSUMS/

4. https://www.spoj.com/problems/FIBOSUM/

5. https://www.spoj.com/problems/LIFEGAME/

6. https://www.spoj.com/problems/NUMQDW/

7. https://www.spoj.com/problems/SEQ/

In the next post, we will see how we can solve this problem ( https://www.spoj.com/problems/SUMSUMS/) using this technique.

Happy Coding ❤️