Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя amir_hamza05

How to solve this Recurrence equations using matrix exponentiation?
Автор amir_hamza05, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 4   Проголосовать: нравится +20 Проголосовать: не нравится

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].

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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 $$$
→ Ответить