akash2504's blog

solving linear recurrences
By akash2504, 11 years ago, In English

how to solve linear recurrences of the type... f(n) = (n-1) * f(n-1) + (2*n-1) * f(n-2) with matrix exponentiation?

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

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

This type of equations can't be solved with matrix exponentiation.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

If you consider a sequence f(0), f(1), f(2), .... You may get pair <f(i), f(i + 1)> from <f(i — 1), f(i)> by multiplying on matrix:

M(n) = { {0, 2n-1}, {1, n-1} }

Every multiplication depends on n. So you don't have a fixed matrix to power it. And it may appear impossible to get exact f(n).

But if you calculate modulo MOD. You will get repetition of matrix after MOD multiplications. So you may calculate product M(0) * M(1) * ... * M(MOD-1) = P. And then calculate final matrix as P^(n / MOD) * M(0) * M(1) ... M(n % MOD). The complexity will be O(MOD + log(n)).

If you use chinese theorem, you can calculate modulo several small numbers: MOD1, MOD2, ... MODk (where MODk is the maximal one). Then total Complexity will be O(log(n) + MODk + k^2).

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

    You will get repetition of matrix after M multiplications

    It seems that it must be MOD instead of M.

    Why? It looks like Fermat's little theorem for matrix. Is it correct?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Fixed.

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

      I don't see any connection with the Fermat little theorem. Repetition will be, because if you calculate modulo MOD, then you may take reminder for any member of multiplication. It is easy to prove that: M(n) % MOD = M(n + MOD) % MOD. So when we calculate by modulo repetition will appear.

      → Reply