5
$\begingroup$

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.

1 Answers 1

9

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} $