# Matrix for recurrence relation

I have recurrence relation for which i need to figure out matrix which can used for matrix exponentiation.

$$f(n) = f(n-1) + f(n-3)$$

Which I think can be written as $$f(n) = a f(n-1) + b f(n-2) + c f(n-3)$$ where values of $$a = 1, b = 0, c = 1$$

| a  b  c |   | f(n-1) |   | f(n) |
| 1  0  0 | x | f(n-2) | = | f(n-1) |
| 0  1  0 |   | f(n-3) |   | f(n-2) |


By following this logic my matrix becomes

| 1  0  1 |
| 1  0  0 |
| 0  1  0 |


which I believe I can use for matrix exponentiation. However, it results in the wrong solution during matrix exponentiation.

But I can use the same matrix for generating series linearly.

    | 1  0  1 |   | f(n-1) |   | f(n) |
| 1  0  0 | x | f(n-2) | = | f(n-1) |
| 0  1  0 |   | f(n-3) |   | f(n-2) |

| 1  0  1 |   | f(n) |     | f(n+1) |
| 1  0  0 | x | f(n-1) | = | f(n) |
| 0  1  0 |   | f(n-2) |   | f(n-1) |


Let $$A$$ be your matrix $$A = \begin{bmatrix} a & b & c\\1 & 0 & 0\\0 & 1 & 0 \end{bmatrix}$$ Starting with given values $$f(0),f(1),f(2)$$, we can find any $$f(n)$$ for $$n \geq 3$$ using matrix exponentiation, i.e. denoting $$x_n = \begin{bmatrix} f(n) & f(n-1) & f(n-2) \end{bmatrix}$$ we have $$x_n = Ax_{n-1}=A^2x_{n-2} = \ldots =A^{n-2}x_2$$ Written differently, $$\begin{bmatrix} f(n) \\ f(n-1) \\ f(n-2) \end{bmatrix} = \begin{bmatrix} a & b & c\\1 & 0 & 0\\0 & 1 & 0 \end{bmatrix}^{n-2}\begin{bmatrix} f(2) \\ f(1) \\ f(0) \end{bmatrix}$$ which means you can generate any window of size three of $$f$$, given $$a,b,c,f(2),f(1),f(0)$$.