Root One

数学中心のブログです。

フィボナッチ数列の母関数とその応用例

フィボナッチ数列とは

\displaystyle 0,1,1,2,3,5,8,13,21,34,55,\cdots

と続く数列で、\displaystyle 0,1 から始まり、以降は前の2項を足した結果となるものです。

\displaystyle 0+1 = 1

\displaystyle 1 +1 = 2

\displaystyle 1 +2 = 3

\displaystyle 2+ 3= 5

\displaystyle 3+ 5 =8

というような感じで順番に決定されていきます。

今回は、このフィボナッチ数列 \displaystyle f_n の「母関数」というものを考え、応用例として \displaystyle a_n = f_{2n} とおくとき

\displaystyle a_{n+2} = 3a_{n+1} - a_{n} \quad (n \geq 0)

という漸化式を導出します。(証明だけならば、母関数を使用する必要はありません。)

この漸化式からわかることは、

フィボナッチ数列は偶数項だけを見て、順番に求めていくことができる.

ということです。

母関数

数列 \displaystyle c_n の母関数とは

\displaystyle f(x) = \sum_{n=0}^\infty c_n x^n

を満たす関数のことを言います。(実は、ほかにもいろいろ種類があります.)

なぜ「母」関数なのかというと、定義から \displaystyle f(x) はすべての \displaystyle c_n の情報を持っているように見えるので、\displaystyle c_n の「母なる」関数というそのままの意味なのでしょう。

面白いのが、\displaystyle c_n がよくわからなくても

「母関数はきれいに求めることができる」

ということがあることです。また、母関数から \displaystyle c_n の性質を調べる研究手法もあり、今回は、その応用例の一つを紹介します。

フィボナッチ数列の母関数

フィボナッチ数列

\displaystyle f_{n+2} = f_{n+1} +f_{n} \qquad (f_0=0 , f_1=1)

を満たす数列として定義します。

母関数を\displaystyle F(x) とおくと、その定義から

\displaystyle F(x) =\sum_{n=0}^\infty f_n x^n \tag{1} \label{eq:Fsumf}

となります。\eqref{eq:Fsumf} に\displaystyle x をかけると

\displaystyle xF(x) =\sum_{n=0}^\infty f_n x^{n+1}

が得られますが、右辺の番号を一つずらすと

\displaystyle x F(x) =\sum_{n=1}^\infty f_{n-1} x^{n} \tag{2} \label{eq:Fsumf2}

となります。\eqref{eq:Fsumf} と\eqref{eq:Fsumf2} と足すと

\displaystyle (1+x) F(x) = f_0 + \sum_{n=1}^\infty (f_n+f_{n-1}) x^n

が得られますが、フィボナッチ数列の漸化式から右辺を変形すると

\begin{align} (1+x) F(x) &= f_0 + \sum_{n=1}^\infty f_{n+1} x^n \\ &= \sum_{n=2}^\infty f_{n} x^{n-1} \\ &= \frac{1}{x} \sum_{n=2}^\infty f_{n} x^{n} \\ &= \frac{1}{x} \left( -f_0 - f_1 x + \sum_{n=0}^\infty f_{n} x^{n} \right) \\ &= \frac{1}{x} \left( -x + \sum_{n=0}^\infty f_{n} x^{n} \right) \\ &= \frac{1}{x} \left( -x + F(x) \right) \\ &= -1 + \frac{F(x)}{x} \end{align}

と変形できます。したがって、

\displaystyle (1+x) F(x) =-1 + \frac{F(x)}{x}

が得られたわけですが、これを \displaystyle F(x) についてとくと

\displaystyle F(x) = \frac{-1}{1+x-\frac{1}{x} } = \frac{x}{1-x - x^2}

となって、これでフィボナッチ数列の母関数を求めることができました。

つまり、

\displaystyle \frac{x}{1-x - x^2} = f_0 + f_1x + f_2x^2 + f_3x^3 + \cdots \tag{3} \label{eq:fcf3}

が得られたことになります。(\displaystyle f_nフィボナッチ数列.)

左辺は、少し面倒ですが、因数分解して部分分数分解すると、テイラー展開できるので、フィボナッチ数列の一般項を係数比較によって求めることもできます。

今得られた母関数 \eqref{eq:fcf3} は常に収束するわけではありません。フィボナッチ数列の増加度はある程度あるので、収束域はあまり大きくありません。正確に収束域を求めることもできますが、とりあえず右辺が収束しそうな値 \displaystyle x=1/4 を\eqref{eq:fcf3} の両辺に代入すると

\displaystyle \frac{4}{11} = f_0 + \frac{f_1}{4} + \frac{f_2}{4^2} + \frac{f_3}{4^3} + \cdots

が得られます。収束が少しきわどくなりますが、\eqref{eq:fcf3} に \displaystyle x=1/2 を入れることも可能です。

\displaystyle 2 = f_0 + \frac{f_1}{2} + \frac{f_2}{2^2} + \frac{f_3}{2^3} + \cdots

さらに欲張って、\eqref{eq:fcf3} に \displaystyle x=1 を入れてしまうと

\displaystyle -1 = f_0 + f_1 + f_2 + f_3 + \cdots

となり、明らかに(実数の世界で)成立しない関係式になってしまいます。

\displaystyle a_n の母関数

最終目的は、\displaystyle a_n = f_{2n} の漸化式を導出することにあるのですが、その準備として \displaystyle a_n の母関数を求めます。

\eqref{eq:fcf3} において、\displaystyle x\displaystyle -x を代入すると

\displaystyle \frac{-x}{1+x - x^2} = f_0 - f_1x + f_2x^2 - f_3x^3 + \cdots

が得られますが、これと \eqref{eq:fcf3} を加えると

\displaystyle \frac{x}{1-x - x^2} + \frac{-x}{1+x - x^2} = 2(f_0 + f_2 x^2 + f_4 x^4 + \cdots )

が得られ、フィボナッチ数列の偶数項だけの母関数が得られます。

左辺を変形すると

\displaystyle \frac{x}{1-x - x^2} + \frac{-x}{1+x - x^2} = \frac{2x^2}{(1-x^2-x)(1-x^2+x)}

となるので、結局

\displaystyle \frac{x^2}{(1-x^2-x)(1-x^2+x)} = f_0 + f_2 x^2 + f_4 x^4 + \cdots

という表示式が得られます。

この式で \displaystyle x\displaystyle \sqrt{x} に置き換えると

\displaystyle \frac{x}{(1-x-\sqrt{x} )(1-x+\sqrt{x} )} = f_0 + f_2 x + f_4 x^2 + \cdots

となり、左辺は

\displaystyle \frac{x}{(1-x-\sqrt{x} )(1-x+\sqrt{x} )} =\frac{x}{(1-x)^2-x} = \frac{x}{x^2-3x+1}

となるので、元に戻れば

\displaystyle \frac{x}{x^2-3x+1} = f_0 + f_2 x + f_4 x^2 + \cdots

が得られます。

\displaystyle a_n = f_{2n}

と定義しているので

\displaystyle \frac{x}{x^2-3x+1} = a_0 + a_1 x + a_2 x^2 + \cdots \tag{4} \label{eq:faa2c}

となり、ようやくこれで目的の母関数が得られたことになります。
漸化式の導出

フィボナッチ数列では、その漸化式を利用して母関数を導きましたが、逆に母関数から漸化式を得ることもできます。

\eqref{eq:faa2c} の両辺に左辺の分母 \displaystyle x^2-3x+1 をかけます。

\displaystyle x = (x^2-3x+1)(a_0+a_1x + \cdots + a_{n-2} x^{n-2} + a_{n-1} x^{n-1}+a_{n} x^{n}+\cdots).

右辺で \displaystyle x^n の項をまとめると

\displaystyle (a_{n-2} -3 a_{n-1} +a_n ) x^n

となりますが、左辺と比較すると、n が2以上ならば0になるはずなので

\displaystyle a_{n-2} -3 a_{n-1} +a_n =0 \quad (n\geq 2)

つまり

\displaystyle a_{n+2} = 3a_{n+1} - a_{n} \quad (n \geq 0)

が得られます。3項間漸化式なので、最初の2項がわかればすべて決定しますが、定義から

\displaystyle a _0 = f_0 = 0 . \quad a_1 = f_2 = 1 .

もすぐにわかります。

実際この漸化式を用いていくつか求めると

\displaystyle a_2 = 3a_1 -a_0 = 3. \quad a_3 = 3a_2 -a_1 = 9-1 = 8 .

となりますが、

\displaystyle f_4= 3 .\quad f_6= 8 .

なので確かに正しい結果であることが確認できます。

このような変形はいくらでもできて、\displaystyle f_{4n} のみの漸化式も得ることができます。
まとめ

数列を研究する際、それだけを見つめていても行き詰ってしまうことがあります。そのようなときは、母関数を考え、関数の力をかりるのも有効かもしれません。