Fibonacci数の母関数

漸化式に $n=0,1,2,\dots$ を順に入れると、
$$ F_2=1+0=1,\quad F_3=1+1=2,\quad F_4=2+1=3,\quad F_5=3+2=5,\quad F_6=5+3=8, $$
$$ F_7=13,\quad F_8=21,\quad F_9=34,\quad F_{10}=55 $$
である。項は急速に大きくなり、$F_{20}=6765$、$F_{30}=832040$ である。

$1-x-x^2$ の係数は、$x^0$ が $1$、$x^1$ が $-1$、$x^2$ が $-1$、それ以外は $0$ である。積の定義から、$(1-x-x^2)\Phi$ の $x^n$ の係数は $F_n-F_{n-1}-F_{n-2}$ である（添字が負になる項は $0$ とする）。小さい $n$ で計算すると、

• $x^0$：$F_0=0$。
• $x^1$：$F_1-F_0=1-0=1$。
• $x^2$：$F_2-F_1-F_0=1-1-0=0$。
• $x^3$：$F_3-F_2-F_1=2-1-1=0$。
• $x^4$：$F_4-F_3-F_2=3-2-1=0$。
  となる。$x^1$ の係数だけが $1$ で、残りは $0$ である。$n\ge2$ では、係数 $F_n-F_{n-1}-F_{n-2}$ は漸化式そのものなので $0$ になる。つまり $(1-x-x^2)\Phi=x$ である。

$\varphi$ は $t^2=t+1$ を満たすので、$\varphi^2=\varphi+1$ である。これを繰り返し使うと
$$ \varphi^3=\varphi\cdot\varphi^2=\varphi^2+\varphi=2\varphi+1,\qquad \varphi^4=2\varphi^2+\varphi=3\varphi+2,\qquad \varphi^5=3\varphi^2+2\varphi=5\varphi+3 $$
である。$\psi$ も $t^2=t+1$ を満たすので、同じ計算で $\psi^5=5\psi+3$ である。よって
$$ \frac{\varphi^5-\psi^5}{\sqrt5}=\frac{5(\varphi-\psi)}{\sqrt5}=\frac{5\sqrt5}{\sqrt5}=5=F_5 $$
である。係数 $5,3$ に $F_5,F_4$ が現れていることにも注意する（一般に $\varphi^n=F_n\varphi+F_{n-1}$）。

$\varphi=1.6180\ldots$、$\psi=-0.6180\ldots$ である。Binet の公式から
$$ F_n-\frac{\varphi^n}{\sqrt5}=-\frac{\psi^n}{\sqrt5} $$
であり、$|\psi|<1$ なので右辺の絶対値は $\frac1{\sqrt5}=0.447\ldots$ 以下である。これは $\frac12$ より小さいので、$F_n$ は $\frac{\varphi^n}{\sqrt5}$ にいちばん近い整数である。たとえば $n=10$ では $\frac{\varphi^{10}}{\sqrt5}=55.0036\ldots$ であり、$F_{10}=55$ に一致する。$n$ が大きくなると差 $\frac{|\psi|^n}{\sqrt5}$ はさらに小さくなる（$n=10$ で $0.0036\ldots$）。

$a_0=0$、$a_1=1$、$a_{n+2}=a_{n+1}+2a_n$ とする。項は $0,1,1,3,5,11,21,43,\dots$ である。
段 1：$(1-x-2x^2)A$ の係数は、$x^0$ で $a_0=0$、$x^1$ で $a_1-a_0=1$、$n\ge2$ で $a_n-a_{n-1}-2a_{n-2}=0$ である。よって $A=\frac{x}{1-x-2x^2}$ である。
段 2：$1-x-2x^2=(1-2x)(1+x)$ であり、
$$ \frac1{1-2x}-\frac1{1+x}=\frac{(1+x)-(1-2x)}{(1-2x)(1+x)}=\frac{3x}{1-x-2x^2} $$
である（この等式は、prf-thm-gff-main の段 3 と同じく、両辺に $(1-2x)(1+x)$ を掛けて確かめる）。
段 3：よって $A=\frac13\bigl(\frac1{1-2x}-\frac1{1+x}\bigr)$ であり、係数を読むと
$$ a_n=\frac{2^n-(-1)^n}3 $$
である。$n=5$ で $\frac{32+1}3=11$、$n=7$ で $\frac{128+1}3=43$ となり、表と一致する。

Lucas 数 $L_0=2$、$L_1=1$、$L_{n+2}=L_{n+1}+L_n$（$2,1,3,4,7,11,18,\dots$）は Fibonacci 数と同じ漸化式を満たす。$(1-x-x^2)\sum L_nx^n$ の係数は、$x^0$ で $L_0=2$、$x^1$ で $L_1-L_0=-1$、$n\ge2$ で $0$ なので、
$$ \sum_{n\ge0}L_nx^n=\frac{2-x}{1-x-x^2} $$
である。分母は $\Phi$ と同じだが、分子が違う。「漸化式が同じなら母関数も同じ」という主張は、この例で破れる。分母は漸化式で決まり、分子は初期値で決まる。実際、$\frac{2-x}{1-x-x^2}=\frac1{1-\varphi x}+\frac1{1-\psi x}$（両辺に $1-x-x^2$ を掛けて確かめられる）から $L_n=\varphi^n+\psi^n$ である。

$n=4$ の表し方は
$$ 1+1+1+1,\quad 1+1+2,\quad 1+2+1,\quad 2+1+1,\quad 2+2 $$
の $5$ 通りである。$n=5$ の表し方を、最後の項で分けて数える。

• 最後が $1$ のもの：残りは $4$ の表し方で、上の $5$ 通りの後ろに $+1$ を付けたもの。
• 最後が $2$ のもの：残りは $3$ の表し方（$1+1+1$、$1+2$、$2+1$ の $3$ 通り）の後ろに $+2$ を付けたもの。
  合わせて $5+3=8$ 通りである。$n=0,1,2,3,4,5$ の個数は $1,1,2,3,5,8$ であり、$F_1,F_2,\dots,F_6$ に一致する。

$C=\frac1{1-x-x^2}$ の係数は、prf-prop-gff-compositions の段 3 から $c_n=c_{n-1}+c_{n-2}$ で順に決まる：$1,1,2,3,5,8,13,21,34,55,89,\dots$ である。したがって $10$ を $1$ と $2$ の順序付きの和で表す方法は $c_{10}=89=F_{11}$ 通りである。Binet の公式を使えば $c_{10}=F_{11}=\frac{\varphi^{11}-\psi^{11}}{\sqrt5}$ であり、ex-gff-rounding により $\frac{\varphi^{11}}{\sqrt5}=88.998\ldots$ にいちばん近い整数として $89$ が得られる。