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

フィボナッチ数列とは

こちらを参照、以下の漸化式で表される数列である。
F₀=0,
F₁=1,
F_n+2=F_n + F_n+1
すなわち、0, 1, 1, 2, 3, 5のように2つ前の項と1つ前の項を足すと次の項になる。

一般項とは

その数列{a_n}のn項目の数字を、nの式で表したもののこと。

導出

特性方程式というものを使って解く方法もあるが、今回はそうでない方法で求める。(特性方程式については、Topic:数列#フィボナッチ数列の一般項の求め方を参照のこと。)

母関数とは

母関数とは、数列{a_n}の数列の情報をもつ係数を使った関数で、すなわち以下のような式のことである。
$\sum _{k=0}^{\infty }{a_{k}x^{k}}={a_{0}x^{0}}+{a_{1}x^{1}}+{a_{2}x^{2}}\cdots$
よって、フィボナッチ数列の母関数は、$f(x)=0x^{0}+1x^{1}+1x^{2}+2x^{3}\cdots$

母関数の閉じた式

閉じた式というのは、有限個の関数の組み合わせによって得られる式のことである。 例として、初項1,公比rの等比数列{b_n}=1,r,r²,r³…について考える。
これらのn項目までの和は、公式より$1\cdot {\frac {1-r^{n}}{1-r}}$
n→∞の極限を考えてみると、|r|<1のとき、rⁿは0になるため、 $\lim _{r\to \infty }1\cdot {\frac {1-r^{n}}{1-r}}={\frac {1}{1-r}}$となる。 だから、形式的に1+r+r²+r³…=${\frac {1}{1-r}}$とする。

f(x)の閉じた式

以下のように計算をする。
$f(x)=0x^{0}+1x^{1}+1x^{2}+2x^{3}\cdots$　　　　　　　　　　・・①
$x\cdot f(x)=$　 　$0x^{1}+1x^{2}+1x^{3}+2x^{4}\cdots$ 　　　　　　 ・・②
$x^{2}\cdot f(x)=$ 　　　　　$0x^{2}+1x^{3}+1x^{4}+2x^{5}\cdots$　　　・・③

そして、①-②-③を計算すると、2乗以上の項は0になるし、0x⁰=0のため、以下の式が得られる。
$f(x)-x\cdot f(x)-x^{2}\cdot f(x)=x$
f(x)でくくって、$f(x)(1-x-x^{2})=x$
$f(x)={\frac {x}{1-x-x^{2}}}$
これがf(x)の閉じた式、母関数である。これを無限級数の形で明示的に表せばはフィボナッチ数列の第n項a_nになる。

等比数列との比較

というわけで、f(x)を${\frac {1}{1-r}}$に近づけることにする。 とりあえず1-x-x²を因数分解してみる。 これが、(1-ax)(1-bx)と因数分解できたとする。したがって、${\frac {x}{1-x-x^{2}}}={\frac {x}{(1-ax)(1-bx)}}$となる。 これを、${\frac {1}{1-r}}$の和の形にしたい。

分解して係数比較

部分分数分解という式変形を使う。
${\frac {x}{1-x-x^{2}}}={\frac {x}{(1-ax)(1-bx)}}={\frac {s}{(1-ax)}}+{\frac {t}{(1-bx)}}$とおくと、両辺を$(1-ax)(1-bx)$倍すると、$x=(1-bx)s+(1-ax)t=s-bsx+t-atx=-(bs+at)x+s+t$

展開して係数比較

したがって、s+t=0,bs+at=-1であるとわかる。
また、$1-x-x^{2}=(1-ax)(1-bx)=1-(a+b)x+abx$より、a+b=1.ab=-1とわかる。

a,bの導出

先程の式から、以下の方程式が導かれる。
${\begin{cases}a+b&=1\\ab&=-1\end{cases}}$
ab=-1を変形する。$a=-{\frac {1}{b}}$
上の式に代入して解く。
$-{\frac {1}{b}}+b=1$
$-{\frac {1}{b}}+{\frac {b^{2}}{b}}=1$
${\frac {-1+b^{2}}{b}}=1$
$-1+b^{2}=b$
$b^{2}-b-1=0$
2次方程式の解の公式に代入する。 $b={\frac {-(-1)\pm {\sqrt {(-1)^{2}-4\times 1\times (-1)}}}{2\times 1}}={\frac {1\pm {\sqrt {5}}}{2}}$
aを代入して求めると、${\frac {1\mp {\sqrt {5}}}{2}}$なので、a>bとすると、 $a={\frac {1+{\sqrt {5}}}{2}}$、$b={\frac {1-{\sqrt {5}}}{2}}$

s,tの導出

a,bを代入し、もう一度連立方程式を解く。
${\begin{cases}s+t&=0\\{\frac {1-{\sqrt {5}}}{2}}s+{\frac {1+{\sqrt {5}}}{2}}t&=-1\end{cases}}$
下の式を2倍する。$(1-{\sqrt {5}})s+(1+{\sqrt {5}})t=-2$・・①
上の式に$(1+{\sqrt {5}})$をかける。$(1+{\sqrt {5}})s+(1+{\sqrt {5}})t=0$・・②
①ー②を計算$\left\{(1-{\sqrt {5}})-(1+{\sqrt {5}})\right\}s=-2$
カッコ内を計算$-2{\sqrt {5}}s=-2$
-2でわる${\sqrt {5}}s=1$
したがって、$s={\frac {1}{\sqrt {5}}}$ これを上の式に代入して、$t=-{\frac {1}{\sqrt {5}}}$

一般項を文字で表す

以上から、得られた変数を代入して、${\frac {x}{1-x-x^{2}}}={\frac {\frac {1}{\sqrt {5}}}{(1-ax)}}-{\frac {\frac {1}{\sqrt {5}}}{(1-bx)}}={\frac {1}{\sqrt {5}}}\left\{{\frac {1}{1-ax}}-{\frac {1}{1-bx}}\right\}$ この{}内の式は、先程の等比数列の無限級数、${\frac {1}{1-r}}=1+r+r^{2}+r^{3}\cdots$であったので、このrにax,bxを代入した式となる。すなわち、 ${\begin{aligned}{\frac {x}{1-x-x^{2}}}&={\frac {\frac {1}{\sqrt {5}}}{(1-ax)}}-{\frac {\frac {1}{\sqrt {5}}}{(1-bx)}}\\&={\frac {1}{\sqrt {5}}}\left\{{\frac {1}{1-ax}}-{\frac {1}{1-bx}}\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\ (1+ax+a^{2}x^{2}+a^{3}x^{3}\cdots )-(1+bx+b^{2}x^{2}+b^{3}x^{3}\cdots )\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\ (a-b)x+(a^{2}-b^{2})x^{2}+(a^{3}-b^{3})x^{3}+\cdots \right\}\\&={\frac {a-b}{\sqrt {5}}}x+{\frac {a^{2}-b^{2}}{\sqrt {5}}}x^{2}+{\frac {a^{3}-b^{3}}{\sqrt {5}}}x^{3}+\cdots \\\end{aligned}}{\frac {a^{n}-b^{n}}{\sqrt {5}}}={\frac {1}{\sqrt {5}}}(a^{n}-b^{n})$
以上から、フィボナッチ数列のn項目は${\frac {a^{n}-b^{n}}{\sqrt {5}}}$となる。

結論

a,bを代入して、 ${\frac {1}{\sqrt {5}}}(a^{n}-b^{n})={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}$ これがフィボナッチ数列の一般項である。