母関数は数列のギフトラッピング

[tex:]

先日はバレンタインデーでした。みなさんはチョコを貰いましたか?

貰った人も貰ってない人も、渡した人も渡してない人も、この時期はいろんなプレゼントが贈られる時期でしょう。

しかしどんなプレゼントを用意したらいいかわからない…というそこのあなた!

母関数をプレゼントしてみてはいかがでしょう?

今回は特別にその作り方を公開します。

みなさんも是非作ってみましょう。

簡単!誰でも作れる母関数

用意するもの

  適量
ペン 1本

材料

お好みの数列 1本

今回はフィボナッチ数列F_nを使って作ります。

フィボナッチ数列とは\begin{align}
F_0&=0\\
F_1&=1\\
F_n&=F_{n-1}+F_{n-2}\ (n\geqq 2)
\end{align}と定義される数列で、簡単に言えば「2つ足し合わせて次の数字をつくる」といった数列です。
0,1,1,2,3,5,8,13,21,\dotsと続きます。

作り方

  1. 数列を並べる $$0,1,1,2,3,5,8,13,\dots$$
  2. x^0, x^1, x^2, x^3,\dotsの項を順番に掛け合わせる$$0x^0,1x^1, 1x^2, 2x^3, 3x^4,5x^5,8x^6,13x^7,\dots$$
  3. すべて足す$$0x^0+1x^1+1x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots$$
  4. お好みで名前をつければ出来上がり!$$F(x)=0x^0+1x^1+1x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots$$

ワンポイントアドバイス

この母関数は項を無限に含んでいるため、プレゼントしようと思っても溢れてラッピングができません。
可能であれば元の数列の特徴を活かして、閉じたxの式にまとめ上げてしまいましょう。

今回であればx^2以降の係数に対してF_n=F_{n-1}+F_{n-2}という関係が利用できます。\begin{align}
F(x)&=F_0x^0+F_1x^1+F_2x^2+F_3x^3+F_4x^4\cdots\\
&=F_0x^0+F_1x^1+(F_0+F_1)x^2+(F_1+F_2)x^3+\cdots\\
&=F_0x^0+F_1x^1+x^2(F_0x^0+F_1x^1+\cdots)+x(F_1x^1+F_2x^2+\cdots)\\
&=F_0x^0+F_1x^1+x^2F(x)+x(F(x)-F_0x^0)\\
&=F_0x^0+F_1x^1+x^2F(x)+xF(x)-F_0x^0\\
&=x+x^2F(x)+xF(x)
\end{align}\begin{align}
(x^2+x-1)\cdot F(x)&=-x\\
F(x)&=\frac{x}{1-x-x^2}
\end{align}このとおり、F(x)=\frac{x}{1-x-x^2}というコンパクトなサイズになりました!
これでプレゼントにもバッチリですね!

しかもこのF(x)をこねくり回してx^nの係数を求めることで、元の数列の一般項が求まっちゃうという優れモノ!
微分積分したりxにいろんな数を代入して遊ぶこともできちゃう!

「気になるあのコに数列をプレゼントしたいけど、一般項や漸化式をそのまま渡すのはカッコ悪い…><」と思っている人は、ぜひ母関数で数列をギフトラップしてプレゼントしよう!!