フィボナッチ数列と2つの母関数
数列anがあったとき、通常の母関数とは
f(x) =Σanxn=a0+a1x+a2x2+…
と表記する。この母関数を使えば、フィボナッチ数列やカタラン数を機械的に計算することができる。
フィボナッチ数列は一般的にan=an-1+an-2で表現され、その母関数の計算は「フィボナッチ数列の母関数」(pdf)にわかりやすく解説されている。
結論として、フィボナッチ数列の母関数は
f(x) = 1/(1-x-x2)
になるため、これをテーラー展開をすることによって、各係数がでて、数列が計算できる。
ところで、フィボナッチ数列は、一般にビネの公式というものがある。(詳細は上記資料を参照)これだとフィボナッチ数列は2つの数字の冪数として表現できる。先ほどの母関数からも複雑な計算をすればビネの公式を見いだせる。ここで、もう一つの母関数を導入すると、ビネの公式が比較的な容易な計算で求められるので紹介しよう。
指数的母関数を
F(x)=Σbnxn/n! =b0+b1x/1!+b2x2/2!+…
と表記する。bn=1ならF(x)=exである。
ここで、フィボナッチ数列の性質から、各式の係数を見比べてF(x)''=F(x)+F'(x)
これは2階微分方程式なので、一般解はAeαx+Beβxとなる。
よって、α,βはx2=x+1を満たす数となる。A,Bはb0=b1=1からもとまる。これより、bnがビネの公式と一致することがわかる。
なお、この指数的母関数の説明は、「はじめての数論」(丸善)を参考にしています。