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.