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

フィボナッチ数列とは

こちらを参照、以下の漸化式で表される数列である。
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}^{\mathrm{\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になるため、 $\underset{r\to \mathrm{\infty }}{\lim }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{array}{cc}a+b& =1\\ ab& =-1\end{array}$
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{array}{cc}s+t& =0\\ \frac{1-\sqrt{5}}{2}s+\frac{1+\sqrt{5}}{2}t& =-1\end{array}$
下の式を2倍する。$(1-\sqrt{5})s+(1+\sqrt{5})t=-2$・・①
上の式に$(1+\sqrt{5})$をかける。$(1+\sqrt{5})s+(1+\sqrt{5})t=0$・・②
①ー②を計算$\{(1-\sqrt{5})-(1+\sqrt{5})\}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}}\{\frac{1}{1-ax}-\frac{1}{1-bx}\}$ この{}内の式は、先程の等比数列の無限級数、$\frac{1}{1-r}=1+r+r^2+r^3\cdots$であったので、このrにax,bxを代入した式となる。すなわち、 $\begin{array}{cc}\frac{x}{1-x-x^2}& =\frac{\frac{1}{\sqrt{5}}}{(1-ax)}-\frac{\frac{1}{\sqrt{5}}}{(1-bx)}\\ & =\frac{1}{\sqrt{5}}\{\frac{1}{1-ax}-\frac{1}{1-bx}\}\\ & =\frac{1}{\sqrt{5}}\{(1+ax+a^2{x}^2+a^3{x}^3\cdots )-(1+bx+b^2{x}^2+b^3{x}^3\cdots )\}\\ & =\frac{1}{\sqrt{5}}\{(a-b)x+(a^2-b^2)x^2+(a^3-b^3)x^3+\cdots \}\\ & =\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{array}\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(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\}$ これがフィボナッチ数列の一般項である。