gol_alu's blog

By gol_alu, history, 11 months ago, In English,

f(n) = n*f(n-1) + f(n-2)

Can this be solved using matrix exponentiation ?

  • Vote: I like it  
  • -4
  • Vote: I do not like it  

11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Short answer: No. This is not a linear recurrence, since n isn't constant. Matrix multiplication can only be used for linear recurrences.

Long answer: Assuming F1 = 0 and F2 = 1, the first few terms of the sequence are: 0, 1, 3, 13,  and 68. This is sequence A058307 in the OEIS. All formulas to calculate the nth term of this recurrence contain factorials of some form, and it seems impossible to make this recurrence linear. Matrix multiplication only works for linear recurrences, therefore the answer is no.