CODEWITHSUNDEEP
algorithmmathrecurrence
pranay
pranay

Reputation: 2369

generating matrix for a recurrence relation

Answered on Math.SE, 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  0  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*f(n-1)+b*f(n-2)+c*f(n-3)+..+someconstant*f(n-k) ?

Thanks.

Upvotes: 2

Views: 2635

Answers (0)

Related Questions