This problem can be solved in logarithmic time by using of such formula
|F_{n+1} F_n|  |k-1 1|^n  |k-1 1|
|           | =|     |  x |     |
|F_n F_{n-1}|  |k-1 0|    |1   0|
and applying fast multiplication. The answer is F_n. This formula generalize corresponding formula for Fibonacci sequence https://www.nayuki.io/page/fast-fibonacci-algorithms. It can be easily proven by induction.

but the formula is wrong when n=2

Edited by author 21.11.2018 23:38

Edited by author 21.11.2018 23:38