メインコンテンツまでスキップ

フィボナッチ数列の第n項

3blue1brown の動画を見て、フィボナッチ数列の一般項の式ってあるのか！と思って調べた。ビネの公式と呼ばれているらしい。

証明を読んでいたら懐かしくなったので、自分でも導いてみた。

Fn=Fn−1+Fn−2F_n = F_{n−1} + F_{n−2}

という三項間漸化式を解きたい。

F(n)−pFn−1 =q(Fn−1−pFn−2)F(n) - pF_{n−1}\ = q(F_{n−1} - pF_{n−2})
F(n)−qFn−1 =p(Fn−1−qFn−2)F(n) - qF_{n−1}\ = p(F_{n−1} - qF_{n−2})

のように 2 つの等比数列として表せたらいい感じに解けるので、そうしたい。

F(n)−pFn−1 =q(Fn−1−pFn−2)F(n) - pF_{n−1}\ = q(F_{n−1} - pF_{n−2})
∴F(n)−(p+q)Fn−1+pqFn−2=0\therefore F(n) - (p+q)F_{n-1} + pqF_{n-2} = 0

ここで

Fn−Fn−1−Fn−2=0F_n - F_{n−1} - F_{n−2} = 0

なので

p+q=1p + q = 1
pq=−1pq = -1

となる。

xx の解が p,qp, q である二次方程式を考えると、

(x−p)(x−q)=0(x-p)(x-q) = 0
∴x2−(p+q)x+pq=0\therefore x^2 - (p+q)x + pq = 0

なので

x2−x−1=0x^2 - x -1 = 0

の解が p,qp, q の値となる。（ pp と qq は順不同。）

これを解くと

x=(p,q)=(1+52,1−52)x = (p, q) =\left( \frac{1 + \sqrt{5}}{2}, \frac{1 - \sqrt{5}}{2} \right)

となる。

ここで一旦最初の方の 2 つの等比数列にもどって、

Fn−pFn−1F_n - pF_{n−1}

は公比が qq の等比数列なので、

Fn−pFn−1F_n - pF_{n−1}
=qn−2(F2−pF1)= q^{n-2}(F_2 - pF_1)
=qn−1= q^{n-1}

となる。同様に

Fn−qFn−1F_n - qF_{n−1}

は公比が qq の等比数列なので、

Fn−qFn−1F_n - qF_{n−1}
=pn−2(F2−qF1)= p^{n-2}(F_2 - qF_1)
=pn−1= p^{n-1}

となる。これら 2 つの式より、

Fn=pn−qnp−qF_n = \frac{p^n - q^n}{p - q}

となる。ここに

(p,q)=(1+52,1−52)(p, q) =\left(\frac{1 + \sqrt{5}}{2}, \frac{1 - \sqrt{5}}{2}\right)

を代入すると、

Fn=15{(1+52)n−(1−52)n}F_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right\}

フィボナッチ数列の第 n 項をプログラムで求める場合、1 項目から普通に計算すると O(n)O(n) だが、ビネの公式で計算すると n が 1 増えるごとに掛け算の回数が 2n 増えるので O(n2)O(n^2) となる（たぶん）。

↑ いやこれは間違いで、1 項目から計算する方法だと第 n 項を求めるために n 回の計算を行う必要があるので O(n)O(n) だが、ビネの公式だと一回の計算で求まるので O(1)O(1) か。

Python での実装はこんな感じ。

1 項目から順に計算する場合。

def fibonacci_iter(n: int) -> int:
    # Returns the (n)th element of the Fibonacci sequence.
    # O(n)
    fib_memo: list[int] = [0, 1]
    iteration = 0
    if n == 0:
        return 0
    if n == 1:
        return 1
    while iteration < n - 1:
        fib_memo.append(sum(fib_memo))
        fib_memo.pop(0)
        iteration += 1
    return fib_memo[1]

ビネの公式を使う場合。

def fibonacci_binet(n: int) -> int:
    # Returns the (n)th element of the Fibonacci sequence.
    # O(n^2)
    # Fails at n = 72 .
    sqrt_of_5 = math.sqrt(5)
    return int(
        (1 / sqrt_of_5)
        * (pow(((1 + sqrt_of_5) / 2), n) - (pow(((1 - sqrt_of_5) / 2), n)))
    )

ビネの公式を使う場合は 5\sqrt{5} という無理数を扱うので浮動小数の誤差の関係で n=72 からおかしくなる。

print(fibonacci_iter(71))    ## 308061521170129
print(fibonacci_binet(71))   ## 308061521170129
print(fibonacci_iter(72))    ## 498454011879264
print(fibonacci_binet(72))   ## 498454011879265

バイナリの仮数部の値を見ていこうかと思ったけど疲れたので今度気が向いたらやるかも。