読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

フィボナッチ数の一般項

フィボナッチ数の一般項は以下の式で表される。
{\displaystyle
a_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)
}

これを展開して、無理数をなくしてあげると以下のようになる。
{\displaystyle
a_n = \frac{1}{2^{n-1}}\sum_{i=0}^{\lfloor \frac{n}{2} \rfloor}\binom{n}{2i+1}~5^i
}

計算量は{O(n^2)}である。例えばpython3で実装すれば以下のようになる。

import scipy.misc as scm
import math

fib = lambda n : int(sum([scm.comb(n,2*i+1,1)*(5**i) for i in range(math.floor((n-1)/2)+1)])/2**(n-1))

print(fib(1000))