母関数に数を代入してよいとき(substituting numbers into generating functions)とは、形式的冪級数の等式 $FG=H$ の $x$ に数 $c$ を入れて、数の等式 $F(c)G(c)=H(c)$ にしてよい条件のことである。$F$ と $G$ が $x=c$ で絶対収束すれば、Mertens の定理によりこの等式が成り立つ(十分条件)。$\frac1{1-x}=\sum x^n$ は係数の等式として常に正しいが、$x=2$ を入れた $-1=1+2+4+\cdots$ や $x=-1$ を入れた $\frac12=1-1+1-\cdots$ は誤りであり、$\sum n!\,x^n$ は $0$ 以外で収束しない。代入できる範囲は係数の増え方で決まり、Fibonacci 数の母関数では $|c|<\frac{\sqrt5-1}2$ である。
前提知識: 無限等比級数, 級数, 数列の極限, 形式的冪級数の積と逆数
高校では、公比 $r$ の無限等比級数について
$$
1+r+r^2+r^3+\cdots=\frac1{1-r}\qquad(|r|<1)
$$
と習う。これは、部分和 $1+r+\cdots+r^N=\frac{1-r^{N+1}}{1-r}$ で $N\to\infty$ としたとき、$|r|<1$ なら $r^{N+1}\to0$ となることから出る。
$r=\frac12$ のとき、部分和は
$$
1,\quad 1.5,\quad 1.75,\quad 1.875,\quad 1.9375,\quad\dots
$$
と $2=\frac1{1-\frac12}$ に近づく。$r=-\frac12$ のとき、部分和は
$$
1,\quad 0.5,\quad 0.75,\quad 0.625,\quad 0.6875,\quad\dots
$$
と、$\frac23=\frac1{1+\frac12}$ の上下を交互に動きながら近づく。
一方、母関数の世界では、形式的冪級数の等式
$$
(1-x)(1+x+x^2+x^3+\cdots)=1,\qquad\text{すなわち}\qquad \frac1{1-x}=\sum_{n\ge0}x^n
$$
が、$x$ についての条件なしに正しい(形式的冪級数の積と逆数)。ここで $x$ は数ではなく、係数の位置の目印である。
では、この等式の $x$ に数を入れてよいか。$x=\frac12$ なら高校の式と一致する。ところが $x=2$ を入れると
$$
-1=1+2+4+8+\cdots
$$
という式が出る。左辺は負なのに右辺の項はすべて正であり、この式は誤りである。この記事の問いは次の 3 つである。
| 問い | 答え |
|---|---|
| 形式的な等式に数を入れてよいのは、どんなときか | 級数が絶対収束するとき(十分条件)→ thm-gfs-substitution |
| 入れてはいけないのは、どんな例か | 反例の表 → ex-gfs-minus-one、ex-gfs-grandi、ex-gfs-factorial |
| 入れてよい範囲は何で決まるか | 係数の増え方 → prop-gfs-fibonacci-range |
以下、この記事では係数も代入する数もすべて実数とする。
形式的冪級数 $F=\sum a_nx^n$ の $x$ に数 $c$ を入れたもの $\sum a_nc^n$ は、数の級数である。級数の値は部分和の極限なので、極限が存在するときにだけ意味がある。
形式的冪級数 $F=\sum_{n\ge0}a_nx^n$ と実数 $c$ について、次のように定める。
絶対収束と、並べ替えると和が変わる条件収束の例は 無限級数の和と収束判定 で扱う。
絶対収束する級数は収束する(Leb26 Proposition 2.5.15、p. 92。本記事では証明しない)。また、収束する級数の項は $0$ に近づく(Leb26 Proposition 2.5.9、p. 90。本記事では証明しない)。後者の対偶「項が $0$ に近づかなければ収束しない」を、反例で使う。
$F=\sum a_nx^n$、$G=\sum b_nx^n$ を実数係数の形式的冪級数、$c$ を実数とし、$F$ と $G$ はどちらも $x=c$ で絶対収束するとする。このとき、次が成り立つ。
方針:$FG$ に $c$ を入れた級数が、2 つの数の級数の「Cauchy 積」になっていることを確かめ、Cauchy 積についての既知の定理を使う。
段 1($FG$ に $c$ を入れた級数の項):形式的冪級数の積の定義から $[x^n](FG)=\sum_{k=0}^na_kb_{n-k}$ である。これに $c^n=c^k\cdot c^{n-k}$ を掛けると
$$
[x^n](FG)\,c^n=\sum_{k=0}^n(a_kc^k)(b_{n-k}c^{n-k})
$$
である。
段 2(Cauchy 積であること):2 つの数の級数 $\sum u_n$、$\sum v_n$ に対して、$w_n:=\sum_{k=0}^nu_kv_{n-k}$ を項とする級数 $\sum w_n$ を、その Cauchy 積という。段 1 の式は、$u_n:=a_nc^n$、$v_n:=b_nc^n$ としたときの $w_n$ である。
段 3(Mertens の定理を使う):Mertens の定理は、「$\sum u_n$ と $\sum v_n$ がどちらも収束し、少なくとも一方が絶対収束するなら、Cauchy 積 $\sum w_n$ は収束して、その和は $\bigl(\sum u_n\bigr)\bigl(\sum v_n\bigr)$ に等しい」という定理である(Leb26 Theorem 2.6.5、p. 104。本記事では証明しない)。仮定から $\sum u_n=\sum a_nc^n$ と $\sum v_n=\sum b_nc^n$ はどちらも絶対収束し、したがって収束する。よって $\sum_n[x^n](FG)c^n$ は収束して $F(c)G(c)$ に等しい。これが 1 である。
段 4(和と定数倍):$[x^n](F+G)c^n=a_nc^n+b_nc^n$ であり、収束する 2 つの級数の項ごとの和は収束して、和の値は 2 つの値の和になる(部分和の極限の和)。定数倍も同じである。これが 2 である。$\square$
この定理は十分条件であり、絶対収束が必要だというわけではない。証明で使った Mertens の定理も、一方だけの絶対収束で足りる。この記事では、分かりやすさのために両方の絶対収束を仮定した。
形式的な等式 $\frac1{1-x}\cdot\frac1{1-x}=\sum_{n\ge0}(n+1)x^n$ がある(積の $x^n$ の係数は $\sum_{k=0}^n1\cdot1=n+1$)。$F=G=\frac1{1-x}=\sum x^n$ は $x=\frac12$ で絶対収束し、$F(\frac12)=2$ である。thm-gfs-substitution により
$$
\sum_{n\ge0}\frac{n+1}{2^n}=1+\frac22+\frac34+\frac48+\cdots=2\cdot2=4
$$
である。部分和 $1,\ 2,\ 2.75,\ 3.25,\ 3.5625,\ 3.75,\dots$ は確かに $4$ に近づく。$x=\frac13$ を入れると、同じく $\sum_{n\ge0}\frac{n+1}{3^n}=\bigl(\frac1{1-\frac13}\bigr)^2=\frac94$ である。
Fibonacci 数 $F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$ の母関数 $\Phi=\sum F_nx^n$ は、形式的な等式 $(1-x-x^2)\Phi=x$ を満たす($(1-x-x^2)\Phi$ の $x^n$ の係数は $F_n-F_{n-1}-F_{n-2}$ で、$n=1$ のとき $1$、それ以外は $0$。Fibonacci数の母関数)。
段 1(絶対収束の確認):$F_n\le2^n$ を $n$ についての帰納法で示す。$F_0=0\le1$、$F_1=1\le2$ であり、$F_n\le2^n$、$F_{n+1}\le2^{n+1}$ なら $F_{n+2}=F_{n+1}+F_n\le2^{n+1}+2^n<2^{n+2}$ である。よって $0< c<\frac12$ なら $F_nc^n\le(2c)^n$ で、$\sum(2c)^n$ は公比 $2c<1$ の等比級数なので収束し、$\Phi$ は $x=c$ で絶対収束する。多項式 $1-x-x^2$ は有限個の項しかないので、どの $c$ でも絶対収束する。
段 2(代入):thm-gfs-substitution により $(1-c-c^2)\Phi(c)=c$ である。$c=\frac1{10}$ とすると $0.89\,\Phi(\frac1{10})=0.1$ であり、両辺を $10\times0.89$ で割って
$$
\sum_{n\ge0}\frac{F_n}{10^{n+1}}=\frac{\Phi(\frac1{10})}{10}=\frac1{89}=0.011235955\ldots
$$
を得る。小数点以下に $0,1,1,2,3,5$ が順に現れ、次の $8$ は後ろの項からの繰り上がりで $9$ になっている。
段 3(別の数で):$c=\frac1{100}$ とすると、同じ計算で $\sum_{n\ge0}\frac{F_n}{100^{n+1}}=\frac1{100^2-100-1}=\frac1{9899}=0.0001010203050813213455\ldots$ であり、2 桁ずつ $00,01,01,02,03,05,08,13,21,34,55$ と並ぶ(その次は $89$ に繰り上がりが加わって $90$ になる)。
図 1 は、部分和 $1+x+\cdots+x^N$ を $\frac1{1-x}$ と比べたものである。$|x|<1$ では $N$ を増やすと部分和が $\frac1{1-x}$ に近づき、$|x|>1$ では離れていく。
部分和 $1+x+\cdots+x^N$($N=2,5,10,20$)と $\frac1{1-x}$。$|x|<1$ の範囲でだけ近づく
次の表の 3 つの反例では、形式的な等式そのものは正しいが、数を入れた等式が成り立たない。
| 外した仮定 | 崩れる主張 | ボックス |
|---|---|---|
| $x=c$ で絶対収束する($c=2$) | $\frac1{1-c}=\sum c^n$ | ex-gfs-minus-one |
| $x=c$ で絶対収束する($c=-1$) | $\frac1{1-c}=\sum c^n$ | ex-gfs-grandi |
| $0$ の近くのある $c\ne0$ で収束する | 「形式的冪級数なら、$0$ の近くの数を入れて関数として使える」 | ex-gfs-factorial |
$(1-x)\sum x^n=1$ は正しい形式的な等式である。$c=2$ では、$\sum x^n$ に $2$ を入れた級数の部分和は $1+2+\cdots+2^N=2^{N+1}-1$ で、限りなく大きくなる。したがって $\sum x^n$ は $x=2$ で収束せず、thm-gfs-substitution の仮定「$x=c$ で絶対収束する」を満たさない。この仮定を外すと、結論「数の等式 $(1-c)\cdot\sum c^n=1$ が成り立つ」は崩れる。左辺の $\sum2^n$ はそもそも数として定まらず、$\frac1{1-2}=-1$ を右辺の和と等しいとする式 $-1=1+2+4+\cdots$ は誤りである。誤っているのは形式的な等式ではなく、代入である。
$c=-1$ を入れると、$\frac1{1-c}=\frac12$ である。一方、$\sum(-1)^n$ の部分和は
$$
1,\quad 0,\quad 1,\quad 0,\quad\dots
$$
と $1$ と $0$ を交互にとり、収束しない。$|c|=1$ なので $\sum|c|^n=1+1+1+\cdots$ も収束せず、thm-gfs-substitution の仮定を満たさない。「$\frac12=1-1+1-1+\cdots$」という式は、級数の値の意味(部分和の極限)では成り立たない。
$F=\sum_{n\ge0}n!\,x^n=1+x+2x^2+6x^3+24x^4+\cdots$ は正しい形式的冪級数であり、定数項が $1$ なので逆数ももつ。逆数の係数を順に計算すると
$$
\frac1F=1-x-x^2-3x^3-13x^4-71x^5-\cdots
$$
である。ところが、$c\ne0$ ならどんな小さい $c$ でも、$F$ は $x=c$ で収束しない。
理由:$n\ge\frac2{|c|}$ となる $n$ では、隣り合う項の絶対値の比が
$$
\frac{(n+1)!\,|c|^{n+1}}{n!\,|c|^n}=(n+1)|c|>2
$$
なので、そこから先の項の絶対値は毎回 2 倍より大きくなり、$0$ に近づかない。収束する級数の項は $0$ に近づくので、$\sum n!\,c^n$ は収束しない。
「形式的冪級数なら、$0$ の近くの数を入れて関数として使える」という主張は、この例で崩れる。それでも、形式的冪級数としての計算(逆数など)は正しく行える。母関数を形式的冪級数として定義しておく利点はここにある(KT17 第 8 章の冒頭と §8.1 は、母関数を形式的冪級数として扱い、多くの場合収束を問わないと断っている)。
高校の無限等比級数の公式が $|r|<1$ に限られることも、この記事の言葉で言い直せる。$\frac1{1-x}=\sum x^n$ は $|x|<1$ で絶対収束するので、この範囲では thm-gfs-substitution により数の等式になる(Lev24 §6.1、p. 423 も、この等式が数として正しいのは $|x|<1$ のときだけだが、母関数としては数を代入しないので問題にならない、と注意している)。
どの $c$ で代入できるかは、係数がどのくらいの速さで大きくなるかで決まる。Fibonacci 数の母関数で、範囲をちょうど決めてみる。$\varphi:=\frac{1+\sqrt5}2=1.618\ldots$、$\psi:=\frac{1-\sqrt5}2$ とし、Binet の公式 $F_n=\frac{\varphi^n-\psi^n}{\sqrt5}$(Fibonacci数の母関数)を使う。$\varphi\psi=-1$ なので $|\psi|=\frac1\varphi=\frac{\sqrt5-1}2=0.618\ldots$ である。
$\Phi=\sum F_nx^n$ と実数 $c$ について、
方針:Binet の公式を使って、$F_n|c|^n$ を 2 つの等比数列で上下から挟む。上からの評価で 1 を、下からの評価で 2 を示す。$c=0$ では 1 は成り立つので、$c\ne0$ とする。
段 1(上下の評価):$|\psi|=\frac1\varphi$ なので、Binet の公式と三角不等式から
$$
\frac{(\varphi|c|)^n-(|c|/\varphi)^n}{\sqrt5}\le F_n|c|^n\le\frac{(\varphi|c|)^n+(|c|/\varphi)^n}{\sqrt5}
$$
である($F_n|c|^n=\frac{|\varphi^n-\psi^n|}{\sqrt5}|c|^n$ で、$|\varphi^n-\psi^n|$ は $\varphi^n-|\psi|^n$ 以上、$\varphi^n+|\psi|^n$ 以下)。
段 2(1 の証明):$|c|<\frac1\varphi$ なら $\varphi|c|<1$ であり、$\varphi>1$ なので $\frac{|c|}\varphi<\varphi|c|<1$ でもある。段 1 の右辺は公比が $1$ より小さい 2 つの等比数列の和の $\frac1{\sqrt5}$ 倍なので、その級数は収束する。0 以上の項の級数で、項がより大きい収束級数の項以下なら収束する(比較判定法、Leb26 Proposition 2.5.16、p. 93)ので、$\sum F_n|c|^n$ は収束する。よって $\Phi$ は $x=c$ で絶対収束する。値は、ex-gfs-one-over-89 の段 2 と同じく thm-gfs-substitution を $(1-x-x^2)\Phi=x$ に使って、$\Phi(c)=\frac{c}{1-c-c^2}$ である($1-c-c^2=(1-\varphi c)(1-\psi c)$ は、$|\varphi c|<1$、$|\psi c|<1$ なので $0$ でない)。
段 3(2 の証明):$|c|\ge\frac1\varphi$ なら $\varphi|c|\ge1$ である。$(|c|/\varphi)^n=(\varphi|c|)^n\varphi^{-2n}$ なので、$n\ge1$ で段 1 の左辺は
$$
\frac{(\varphi|c|)^n\bigl(1-\varphi^{-2n}\bigr)}{\sqrt5}\ge\frac{1\cdot(1-\varphi^{-2})}{\sqrt5}=0.276\ldots
$$
である($(\varphi|c|)^n\ge1$、$\varphi^{-2n}\le\varphi^{-2}$ を使った)。よって項 $F_nc^n$ の絶対値は $0.27$ より小さくならず、$0$ に近づかない。収束する級数の項は $0$ に近づくので、$\Phi$ は $x=c$ で収束しない。$\square$
$c=0.5$ なら $\frac{c}{1-c-c^2}=\frac{0.5}{0.25}=2$ である。部分和は $N=10$ で $1.772\ldots$、$N=20$ で $1.9726\ldots$、$N=40$ で $1.99960\ldots$ と速く $2$ に近づく。$c=0.6$ は $\frac1\varphi=0.618\ldots$ より少し小さいので収束するが、$\frac{0.6}{1-0.6-0.36}=15$ への近づき方は遅い($N=20$ で $6.77\ldots$、$N=60$ で $12.48\ldots$)。$c=0.65$ は $\frac1\varphi$ より大きいので、部分和は限りなく大きくなる。
$\sum_{n\le N}F_nc^n$ の部分和。$c=0.5,\ 0.6$ は収束し(点線が極限)、$c=0.65$ は発散する
逆に言えば、母関数が収束する範囲の境目 $\frac1\varphi$ から、係数が $\varphi^n$ の速さで増えることが読み取れる。
最後に、逆向きの事実を 1 つ述べておく。$0$ を含むある区間で収束する 2 つの冪級数が、その区間で関数として等しければ、係数もすべて等しい(冪級数の一致の定理。冪級数 の記事の命題「中心に近づく点列の上で0になる冪級数」。本記事では証明しない)。したがって、収束する母関数については、微分などの解析の道具で形式的な等式を示してもよい。
係数の比から収束半径を求める方法は 関数の近似とテイラー展開 で扱う。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する