Matrix for recurrence relation

Question

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) |

Can someone please help me to know where I am going wrong?

Answer 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)$.