Hemanth_1's blog

By Hemanth_1, history, 5 years ago, In English

I was trying to solve this problem, find the n'th term of the following recurrence:

F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3) + n*n*(n+1)

a,b,c and the first 3 numbers in the sequence are given as the input, n can be upto 10^18 . I know that problems involving linear recurrences can be solved using matrix exponentiation, even when there are multiple sequences involved. So, in this case, if I could somehow express n*n*(n+1) as a linear recurrence as well, solving this problem becomes simple. However, I'm not able to do that, can someone help me with this ? Also, if a method to find a recurrence relation, given a closed form, exists, please mention that as well. Thanks in advance.

Full text and comments »

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