om1429888's blog

need suggestions about applying matrix exponentiation to non linear relations

By om1429888, history, 2 years ago, In English

Hi guys. We all know that matrix exponentiation can be used to find Nth term of a recurrent relation in logN time, this is generally used to find Nth fibonacci in logN time where N can be as large as 1e18(obviously it is modulo something), now fibonacci is represented as f(n-1)+f(n-2),but what is relation isnt linear, it can be for example, f(n-1)+f(n-2)+f(n-1)*f(fn-2). i tried and could'nt find a solution, so any suggestions>

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

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it
Newbies
Me in a round
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    lmao, thanks for the advice.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Me solving those problems
    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Mathematical savvy should help you. For example Solving Non Linear Recurrence Relation. In our case we can rewrite the recurrence as

$$$f[n] + 1 = f[n-1] * f[n-2] + f[n-1] + f[n-2] + 1 = (f[n-1] + 1) * (f[n-2] + 1)$$$

Or if we denote

$$$g_n = f[n] + 1$$$

we have

$$$ g_n = g_{n-1} g_{n-2}$$$

If our initial conditions are

$$$ f[0] = b, f[1] = a$$$

(and nonzero) then

$$$f[n] = (a + 1)^{F_n} (b + 1)^{F_{n-1}} - 1$$$

where $F_n$ is $$$n$$$-th Fibonacci number ($$$F_2 = F_1 = 1$$$). The case with zero $$$a$$$ or $$$b$$$ is simple.

→ Reply