0
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks, i missed out last multiplication with initial set of matrix [fn, fn-1, fn-2] $\endgroup$
    – ASB
    Feb 15 '19 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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