a_n + b_n*Sqrt[5] = (3 + Sqrt[5])^n = (3 + Sqrt[5])*(3 + Sqrt[5])^(n-1) = (3 + Sqrt[5])*(a_{n-1} + b_{n-1} * Sqrt[5])

=

(3*a_{n-1} + 5*b_{n-1}) + (a_{n-1} + 3*b_{n-1}) * Sqrt[5]


M := {{3, 5}, {1, 3}}

とおけば、

{a_n, b_n} = M * {a_{n-1}, b_{n-1}}

が成り立ちます。

{a_n, b_n} = M^(n-1) * {a_1, b_1}

M^(n-1) は繰り返し2乗法で計算すれば、 Θ(log(n)) で計算できる。