Zenn
🧮

フィボナッチ数列の一般項をもとに値を計算するコード

2024/08/18に公開
math
tech

まえがき

最近、数学ガールを読んでいます
扱うテーマは難しいですが、それを噛み砕いて説明してくれているおかげで読みやすくて良いです
今回は、そこで出てきたフィボナッチ数列を少し掘り下げたいと思います

概要

  • フィボナッチ数列の一般項を使って値を計算するコードを書いた
  • 一般項の定義をそのまま実装すると無理数が出てきて違和感があるので、式変形してからコードにした

フィボナッチ数列の一般項

フィボナッチ数列F_n = F_{n-1} + F_{n-2}は一般項が存在し、以下の式で表されます

F_n = \frac{1}{\sqrt{5}} \biggl\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \biggr\}

この一般項をもとに、F_nを求めるpythonコードを書くと以下のようになります

fibonacci.py
import math
import sys

def fibonacci(n):
    sqrt_5 = math.sqrt(5)
    result = (((1 + sqrt_5) / 2) ** n - ((1 - sqrt_5) / 2) ** n) / sqrt_5
    return int(result)

if __name__ == "__main__":
    n = int(sys.argv[1])
    print(fibonacci(n))

このままでも問題なく動作はしますが、自然数を入力として自然数を返す関数なのに、計算途中に\sqrt{5}が入っているのは少し違和感があります
そこで、\sqrt{5}を含まない形に式変形することを考えてみます

\sqrt{5}を含まない形に式変形

まずは二項定理を使って、n乗の箇所を和に書き換えます

F_n = \frac{1}{\sqrt{5}} \biggl\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \biggr\} \\ = \frac{1}{2^n \sqrt{5}} \biggl\{ \left(1+\sqrt{5} \right)^n - \left(1-\sqrt{5} \right)^n \biggr\} \\ = \frac{1}{2^n \sqrt{5}} \biggl\{ \sum_{k=0}^n {}_n \mathrm{C}_k (\sqrt{5})^k - \sum_{k=0}^n {}_n \mathrm{C}_k (-\sqrt{5})^k \biggr\} \\ = \frac{1}{2^n \sqrt{5}} \biggl\{ \sum_{k=0}^n {}_n \mathrm{C}_k \bigl( (\sqrt{5})^k - (-\sqrt{5})^k \bigr) \biggr\}

ここで、kが偶数（mを自然数として、k=2m）のとき、(\sqrt{5})^k - (-\sqrt{5})^k = 5^m - 5^m =0となるので、kが奇数の場合のみ考えれば良いことが分かります
一方、kが奇数（k=2m+1）の時、(\sqrt{5})^k - (-\sqrt{5})^k = 2(\sqrt{5})^{2m+1}=2\sqrt{5} \sdot 5^mとなります

k=2m+1とおいてF_nの式変形を続けると、n \geq 1のとき、

F_n = \frac{1}{2^n \sqrt{5}} \biggl\{ \sum_{k=0}^n {}_n \mathrm{C}_k \bigl( (\sqrt{5})^k - (-\sqrt{5})^k \bigr) \biggr\} \\ = \frac{1}{2^n \sqrt{5}} \bigg( \sum_{m=0}^{\lfloor \frac{n-1}{2} \rfloor} {}_n \mathrm{C}_{2m+1} 2\sqrt{5} \sdot 5^m \bigg) \\ = \frac{1}{2^{n-1}} \bigg( \sum_{m=0}^{\lfloor \frac{n-1}{2} \rfloor} {}_n \mathrm{C}_{2m+1} 5^m \bigg) (n \geq 1)

となり、一般項を\sqrt{5}を含まない形で表すことができました（ただし、\lfloor \frac{n-1}{2} \rfloorは床関数）

\sqrt{5}を含まない形で実装

式変形の結果をもとに、実装を修正します

fibonacci.py
def fibonacci(n):
    if n == 0:
        return 0

    result = 0
    half_floor = math.floor((n - 1) / 2)
    for m in range(half_floor + 1):
        result += math.comb(n, 2 * m + 1) * (5 ** m)
    result //= 2 ** (n - 1)
    return result

if __name__ == "__main__":
    n = int(sys.argv[1])
    print(fibonacci(n))

実装が合っているか確認するため、いくつかの値で実行して確認します

$ python fibonacci.py 1
1
$ python fibonacci.py 2
1
$ python fibonacci.py 3
2
$ python fibonacci.py 4
3
$ python fibonacci.py 5
5
$ python fibonacci.py 20
6765

Wikipediaによると、フィボナッチ数列の第20項の値は6765なので、問題なく動作していることが確認できました

Discussion