# generating matrix for a recurrence relation

for the recurrence f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4) , how can one get the generating matrix so that it can be solved by matrix exponentiation?

For f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3) the corresponding generating matrix is:

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


so how to get the same for required recurrence? Also what should be the procedure for any recurrence which may be of the form :

$f(n)=a_1f(n-1)+a_2f(n-2)+a_3f(n-3)+..+a_kf(n-k)$ ?

Thanks.

-

You can easily verify the answer below by applying the matrix multiplication. State transition matrix for the given recurrence-relation is $$\begin{bmatrix} f(n) \\ f(n-1) \\ f(n-2) \\ \vdots \\ f(n-(k-1)) \end{bmatrix} = \begin{bmatrix} a_1 & a_2 & a_3 & \dots & a_{k-1} & a_k \\[0.3em] 1 & 0 & 0 & \dots & 0 & 0 \\[0.3em] 0 & 1 & 0 & \dots & 0 & 0 \\[0.3em] 0 & 0 & 1 & \dots & 0 & 0 \\[0.3em] \vdots & & & \ddots & 0 & 0 \\[0.3em] 0 & 0 & 0 & \dots & 1 & 0 \\[0.3em] \end{bmatrix} \begin{bmatrix} f(n-1) \\ f(n-2) \\ f(n-3) \\ \vdots \\ f(n-k) \end{bmatrix}$$