*Find f(n): nth Fibonacci number.* The problem is quite easy when **n** is relatively small. We can use simple recursion, `f(n) = f(n-1) + f(n-2)`

, or we can use dynamic programming approach to avoid the calculation of same function over and over again. But what will you do if the problem says, **Given 0 < n < 10⁹, find f(n) mod 999983?** Dynamic programming will fail, so how do we tackle this problem?

First let’s see how matrix exponentiation can help to represent recursive relation.

**Prerequisites:**

- Given two matrices, know how to find their product. Further, given the product matrix of two matrices, and one of them, know how to find the other matrix.
- Given a matrix of size
**d X d**, know how to find its nth power in**O(d3log(n))**.

**Patterns:**

At first we need a recursive relation and we want to find a matrix **M** which can lead us to the desired state from a set of already known states. Let’s assume that, we know the **k** states of a given recurrence relation and we want to find the **(k+1)th** state. Let **M** be a **k X k** matrix, and we build a matrix **A:[k X 1]** from the known states of the recurrence relation, now we want to get a matrix **B:[k X 1]** which will represent the set of next states, i. e. **M X A = B** as shown below:

```
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
M X | f(n-2) | = | f(n-1) |
| ...... | | ...... |
| f(n-k) | |f(n-k+1)|
```

So, if we can design **M** accordingly, our job will be done! The matrix will then be used to represent the recurrence relation.

**Type 1:** Let’s start with the simplest one, `f(n) = f(n-1) + f(n-2)`

We get, `f(n+1) = f(n) + f(n-1)`

. Let’s assume, we know `f(n)`

and `f(n-1)`

; We want to find out `f(n+1)`

. From the situation stated above, matrix **A** and matrix **B** can be formed as shown below:

```
Matrix A Matrix B
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
```

[Note: Matrix **A** will be always designed in such a way that, every state on which `f(n+1)`

depends, will be present] Now, we need to design a **2X2** matrix **M** such that, it satisfies **M X A = B** as stated above. The first element of **B** is `f(n+1)`

which is actually `f(n) + f(n-1)`

. To get this, from matrix **A**, we need, **1 X f(n)** and **1 X f(n-1)**. So the first row of **M** will be **[1 1]**.

```
| 1 1 | X | f(n) | = | f(n+1) |
| ----- | | f(n-1) | | ------ |
```

[Note: —– means we are not concerned about this value.] Similarly, 2nd item of **B** is `f(n)`

which can be got by simply taking **1 X f(n)** from **A**, so the 2nd row of **M** is [1 0].

```
| ----- | X | f(n) | = | ------ |
| 1 0 | | f(n-1) | | f(n) |
```

Then we get our desired **2 X 2** matrix **M**.

```
| 1 1 | X | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
```

These matrices are simply derived using matrix multiplication.

**Type 2:**

Let’s make it a little complex: find `f(n) = a X f(n-1) + b X f(n-2)`

, where **a** and **b** are constants. This tells us, `f(n+1) = a X f(n) + b X f(n-1)`

. By this far, this should be clear that the dimension of the matrices will be equal to the number of dependencies, i.e. in this particular example, again 2. So for **A** and **B**, we can build two matrices of size **2 X 1**: