$$$F(n) + 1 = (1 + F(n - 1)(1 + F(n - 2))$$$

Lets say $$$t_n = F_n + 1$$$, then $$$t_n = t_{n - 1} * t_{n - 2} $$$, expanding $$$t_n$$$ it can be realised that $$$t_n = t_0^{p_n} t_1^{q_n}$$$, where $$$p_n, q_n$$$ follows fibonacci recurrence.

Add 1 on both sides

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

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

let g(n)=1+F(n)

-> g(n)=g(n-1)*g(n-2)

Now taking log on both sides

log(g(n))=log(g(n-1))+log(g(n-2))

let h(n)=log(g(n))

h(n)=h(n-1)+h(n-2)

Now the nth term of h can be found using matrix exponentation in O(log(n))

Like so:

First, factor the recurrence to get F(n)=(F(n-1)+1)(F(n-2)+1)-1.

Then, set G(n)=F(n)+1; we find G(n)=(F(n-1)+1)(F(n-2)+1)=G(n-1)G(n-2).

Let A=G(1)=F(1)+1 and B=G(2)=F(2)+1. Since G(n) will always be the product of some earlier terms, we can make a function x(n) and y(n) so that G(n)=A^(x(n))*B^(y(n)).

We have the initial values x(1)=1,x(2)=0,y(1)=0,y(2)=1 and the recurrence relations x(n)=x(n-1)+x(n-2),y(n)=y(n-1)+y(n-2). This is the same as Fibonacci but with different starting values.

Use matrix exponentiation to find x(n) and y(n), and then fast exponentiation to find A^(x(n))*B^(y(n)); the answer is A^(x(n))*B^(y(n))-1.

Auto comment: topic has been updated by anupamshah_ (previous revision, new revision, compare).