0205132人目の素数さん
2019/12/03(火) 23:59:07.60ID:b5QWSNPE=
(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)) で計算できる。