フィボナッチ数列と２つの母関数

数列a_nがあったとき、通常の母関数とは

f(x) =Σa_nxⁿ=a₀+a₁x+a₂x²+…

と表記する。この母関数を使えば、フィボナッチ数列やカタラン数を機械的に計算することができる。

フィボナッチ数列は一般的にa_n=a_n-1+a_n-2で表現され、その母関数の計算は「フィボナッチ数列の母関数」（pdf)にわかりやすく解説されている。

結論として、フィボナッチ数列の母関数は

f(x) = 1/(1-x-x²)

になるため、これをテーラー展開をすることによって、各係数がでて、数列が計算できる。

ところで、フィボナッチ数列は、一般にビネの公式というものがある。（詳細は上記資料を参照）これだとフィボナッチ数列は２つの数字の冪数として表現できる。先ほどの母関数からも複雑な計算をすればビネの公式を見いだせる。ここで、もう一つの母関数を導入すると、ビネの公式が比較的な容易な計算で求められるので紹介しよう。

指数的母関数を

 F(x)=Σb_nxⁿ/n! =b₀+b₁x/1!+b₂x²/2!+…

と表記する。b_n=1ならF(x)=e^xである。

ここで、フィボナッチ数列の性質から、各式の係数を見比べてF(x)''=F(x)+F'(x) 

これは２階微分方程式なので、一般解はAe^αx+Be^βxとなる。

よって、α,βはx²=x+1を満たす数となる。A,Bはb₀=b₁=1からもとまる。これより、b_nがビネの公式と一致することがわかる。

なお、この指数的母関数の説明は、「はじめての数論」（丸善）を参考にしています。