amir_hamza05's blog

How to solve this Recurrence equations using matrix exponentiation?
By amir_hamza05, history, 5 years ago, In English

I can solve this recurrence equations f(N)=f(N-1)+f(N-2)+C using matrix exponentiation.when C is constraint.But when i use N instant of constraint C or when our recurrence equations look like f(N)=f(N-1)+f(N-2)+N then how to solve this Recurrence equations using matrix exponentiation?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 4   Vote: I like it +20 Vote: I do not like it

Consider the following matrix:

0 1 0 0
1 1 1 0
0 0 1 1
0 0 0 1

It transforms a vector [f_{n-2}, f_{n-1}, n, 1] into [f_{n-1}, f_{n-1} + f_{n-2} + n, n + 1, 1].

→ Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

You can make this transformations to delete $$$n$$$.

$$$ f_n=f_{n-1}+f_{n-2}+n \\ f_{n-1}=f_{n-2}+f_{n-3}+(n-1) \\ f_n-f_{n-1}=f_{n-1}+f_{n-2}+n-f_{n-2}-f_{n-3}-n+1 \\ f_n=2f_{n-1}-f_{n-3}+1 $$$
→ Reply