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

この記事は, 旧ブログから移植された記事です. よって, その内容として, 旧ブログに依存した文脈が含まれている可能性があります. 予めご了承下さい.

フィボナッチ数列を以下の漸化式で定義する.

フィボナッチ数列

fn+2=fn+1+fn (n≥0)f_{n+2} = f_{n+1} + f_n\ (n\geq 0)

ここで, 初項と第二項をそれぞれ a1=1,a2=1a_1=1, a_2=1 とする. 各項を fn+2→c2、fn+1→c、fn→1f_{n+2}\rightarrow c^2、f_{n+1}\rightarrow c、f_n\rightarrow 1 と置き換えると c2=c+1(1)c^2=c+1\tag{1} が得られる. この解は c=1±52c=\dfrac{1\pm{\sqrt{5}}}{2} となる. ここで, ψ=1−52,ϕ=1+52\psi = \dfrac{1-\sqrt{5}}{2}, \phi = \dfrac{1+\sqrt{5}}{2} と置く. フィボナッチ数列の漸化式の特性方程式の解は (1)(1) の解より ψ,ϕ\psi, \phi であるから fn+2=fn+1+fn⇔{fn+2−ψfn+1=ϕ(fn+1−ψfn)fn+2−ϕfn+1=ψ(fn+1−ϕfn)f_{n+2}=f_{n+1}+f_{n}\Leftrightarrow\begin{cases}f_{n+2}-\psi f_{n+1}=\phi(f_{n+1}-\psi f_n) \\ f_{n+2}-\phi f_{n+1}=\psi(f_{n+1}-\phi f_n)\end{cases} と変形できる. いま bn=fn+1−ψfn,cn=fn+1−ϕfnb_n=f_{n+1}-\psi f_n, c_n=f_{n+1}-\phi f_n と置くと次の漸化式が得られる. {bn+1=ϕbncn+1=ψcn\begin{cases}b_{n+1}=\phi b_n\\c_{n+1}=\psi c_n\end{cases} また f1=1,f2=1f_1=1, f_2=1 より {b1=f2−ψf1=1−ψc1=f2−ϕf1=1−ϕ\begin{cases}b_1=f_2-\psi f_1=1-\psi\\ c_1=f_2-\phi f_1=1-\phi\end{cases} として, 数列 bn{b_n} と数列 cn{c_n} の初項が求まる. 故に, 数列 bn{b_n} は初項 1−ψ1-\psi, 公比 ϕ\phi の等比数列であるから, bn=(1−ψ)ϕn−1b_n = (1-\psi)\phi^{n-1}, 数列 cn{c_n} は初項 1−ϕ1-\phi, 公比 ψ\psi の等比数列であるから, cn=(1−ϕ)ψn−1c_n = (1-\phi)\psi^{n-1} といえる. さらに bn,cnb_n, c_n を上記の定義より代入すると, {ϕn=bn=fn+1−ψfnpsin=cn=fn+1−ϕfn\begin{cases} \phi^n=b_n=f_{n+1}-\psi f_n\\psi^n=c_n=f_{n+1}-\phi f_n\end{cases} が得られる. 上の式から下の式を引くと ϕn−ψn=−ψfn+ϕfn=(ϕ−ψ)fn\phi^n-\psi^n=-\psi f_n+\phi f_n=(\phi-\psi)f_n であるから, 一般項 fnf_n は fn=1ϕ−ψ(ϕn−ψn)f_n=\dfrac{1}{\phi-\psi}( \phi^n-\psi^n) ∴\therefore ψ,ϕ\psi, \phi を上記の定義より代入すると, 以下のフィボナッチ数列の一般項が求まる.

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

fn=15{(1+52)n−(1−52)n}f_n=\dfrac{1}{\sqrt{5}}\left\{(\dfrac{1+\sqrt{5}}{2})^{n}-(\dfrac{1-\sqrt{5}}{2})^{n} \right\}

数値計算で確認してみよう.

{-# OPTIONS_GHC -Wall #-}

import System.Random (getStdRandom, randomR)
import System.IO (stderr)
import Test.HUnit (Test (TestList), (~:), (~?=), runTestText, putTextToHandle)
import Control.Monad (void)

fibGeneralTerm :: Int -> Integer
fibGeneralTerm = let phi = (1 + sqrt 5) / 2 :: Double in floor.(+0.5).(/ sqrt 5).(phi ^^)

fib :: [Integer]
fib = 0:1:zipWith (+) fib (tail fib)

mkTestList :: Int -> Int -> Int -> IO Test
mkTestList b l times = TestList <$> loop 1
    where 
        loop i 
            | i <= times = do 
                r <- getStdRandom $ randomR (b, l) 
                (:) ("fib test: " ++ show i ++ ", value: " ++ show r ~: fibGeneralTerm r ~?= fib !! r) <$> loop (succ i) 
            | otherwise = return []

main :: IO ()
main = mkTestList 0 50 5 >>= void.runTestText (putTextToHandle stderr False)
cases: 5  Tried: 5  Errors: 0  Failures: 0

上で導出した式の第二項の最大値は 15≈0.447\displaystyle \dfrac{1}{\sqrt{5}} \approx 0.447 が最大であることから, 正確な整数値を求めるのには第二項を略してしまって 0.50.5 を加え, 床関数を作用させれば十分である1. 上のコードでもそれを利用している.

fn=⌊ϕn5+12⌋f_n=\left\lfloor \dfrac{\phi^{n}}{\sqrt{5}}+\dfrac{1}{2} \right\rfloor

ただし, 計算処理内で浮動小数点数による加算を用いていることから, 大きな値になればなるほど絶対誤差が生じていくことになる. 今回の実行結果も, たまたまその誤差が埋もれただけであってfibGeneralTermの実行結果に対する厳密な信憑性はない.

  1. 参考: ウィキペディア - フィボナッチ数↩︎