漸化式と母関数：特性方程式・行列の冪・Fibonacci 数・分割数

0. この記事の要点

「前の項から次の項を決める規則」で並ぶ数列について、100 番目の項を 99 回の計算なしに一気に求められないか、という話です。Fibonacci 数のような身近な数列を例に、規則から $n$ 番目の項の式を作る方法を、行列や、数列を 1 つの式にまとめる道具（母関数）まで広げて説明します。読み終えると、典型的な漸化式の一般項を自分で求められ、Fibonacci 数の約数の性質や分割の数え方の恒等式も、計算で示せるようになります。

• 隣り合う項の関係 $a_{n+1}=pa_n+q$ は、固定点 $c=pc+q$ を引けば等比数列に帰着します。3 項間の線形漸化式 $a_{n+2}=pa_{n+1}+qa_n$ は、特性方程式 $x^2=px+q$ の解 $\alpha,\beta$ で $a_n=A\alpha^n+B\beta^n$（重解のときは $(A+Bn)\alpha^n$）と書けます。解全体が 2 次元の空間をなす、というのが理由です。
• 行列 $M$ の冪は、$x^n$ を特性多項式で割った余り $u_nx+v_n$ から $M^n=u_nM+v_nI$ と計算できます。Fibonacci 数、グラフの歩道の数、重根の $n\alpha^n$（Jordan 細胞）がこの 1 つの計算で現れます。
• 分数型の漸化式 $a_{n+1}=\tfrac{pa_n+q}{ra_n+s}$ は、固定点を使って 2 項間の等比型に直せます。
• Fibonacci 数の最大公約数は $\gcd(F_m,F_n)=F_{\gcd(m,n)}$。証明は、行列の冪から出る加法公式と、互除法の考え方だけです。
• 母関数 $\sum a_nx^n$ は、数列を 1 つの関数にまとめます。漸化式を満たす数列の母関数は有理関数で、$x$ に数を代入してよい範囲（収束する範囲）も具体的に決まります。
• Euler の分割恒等式（奇数の部分への分割の数 = 相異なる部分への分割の数）は、母関数の積の計算だけで示せます。

この記事で使う事前知識

• ベクトル空間: 足し算とスカラー倍ができ、その計算規則を満たす集合。→ ベクトル空間
• 行列の積: 左の行列の行と右の行列の列の成分を掛けて足したものを並べて作る行列。→ 行列の積
• 行列式: 正方行列に決まる 1 つの数で、$2\times2$ では $ad-bc$。0 でないことが 1 次独立の判定に使える。→ 行列式
• 特性多項式: 正方行列 $M$ に対する $\det(xI-M)$。→ 特性多項式
• 形式的冪級数: 収束を考えず、$\sum a_nx^n$ を係数の列として扱うもの。→ 形式的冪級数環
• 多項式の割り算: 割り算の商と余り（余りの次数は割る式より小さい）。→ 多項式の割り算と高次方程式

1. 動機：漸化式の「解」とは何か

漸化式 $a_{n+2}=a_{n+1}+a_n$（Fibonacci 数）は、初項を与えれば全項が決まる、という意味で「解がある」ことは明らかです。しかし「$n$ 番目の項はいくつか」を知るには、$n-2$ 回の足し算をするしかないのでしょうか。高校では、特性方程式という手順で $F_n=\tfrac{1}{\sqrt5}\bigl(\phi^n-\psi^n\bigr)$（$\phi,\psi=\tfrac{1\pm\sqrt5}2$）という閉じた式（Binet の公式）を得ますが、この手順は暗記の対象になりがちです。なぜ $\alpha^n$ という形を仮定してよいのか、重解のときになぜ $n\alpha^n$ が加わるのか。

この記事は、その理由を次の 3 つの視点から説明します。

1. ベクトル空間として：漸化式を満たす数列全体は 2 次元のベクトル空間で、$\alpha^n$ と $\beta^n$ はその基底になる。
2. 行列として：漸化式は 2 次の行列の冪 $M^n$ の計算で、$M^n$ は $x^n$ を特性多項式で割った余りで書ける。
3. 母関数として：数列 $(a_n)$ を冪級数 $\sum a_nx^n$ に写すと、漸化式は多項式の掛け算になり、解は有理関数として一目でわかる。

使う道具は前の章の、多項式の除法の原理（多項式の除法の原理（定理 2.2）［多項式の割り算と高次方程式］）、複素数係数の 2 次方程式（複素数係数の 2 次方程式（定理 4.2）［多項式の割り算と高次方程式］）、数列の和と差分（数列）です。この記事では、項番号を $0$ から始める数列 $(a_n)_{n\ge0}$ も使います。

2. 線形漸化式と特性方程式

定理 2.1（1 次の 2 項間漸化式）✓

$p,q$ を複素数とし、数列 $(a_n)_{n\ge0}$ が $a_{n+1}=pa_n+q$ を満たすとする。$p=1$ なら $a_n=a_0+nq$。$p\ne1$ なら、$c=\dfrac q{1-p}$（$c=pc+q$ を満たす固定点）として

$$a_n=p^n(a_0-c)+c.$$

証明（定理 2.1）

$p=1$ のときは $a_{n+1}=a_n+q$ で等差数列。$p\ne1$ のとき $b_n=a_n-c$ とおくと、$b_{n+1}=pa_n+q-c=p(a_n-c)+(pc+q-c)=pb_n$（$pc+q=c$ より）。よって $b_n=p^nb_0$（帰納法）で、$a_n=c+p^n(a_0-c)$ です。

∎

次の定理は、$\alpha^n$ の形の解を探せば十分だ、という主張です。証明の前半は線形代数の言葉（解全体が 2 次元の空間をなす）を使いますが、要は「最初の 2 項で数列が決まるので、独立な解が 2 つ見つかれば全部の解が書ける」ということです。

定理 2.2（3 項間の線形漸化式と特性方程式）✓

$p,q$ を複素数、$q\ne0$ とし、数列 $(a_n)_{n\ge0}$ が $a_{n+2}=pa_{n+1}+qa_n$ を満たすとする。特性方程式 $x^2-px-q=0$ の 2 解を $\alpha,\beta$ とする（複素数係数の 2 次方程式（定理 4.2）［多項式の割り算と高次方程式］）。

• $\alpha\ne\beta$ のとき、$a_n=A\alpha^n+B\beta^n$ となる定数 $A,B$ がただ 1 組ある（$A+B=a_0$、$A\alpha+B\beta=a_1$）。
• $\alpha=\beta$ のとき、$a_n=(A+Bn)\alpha^n$ となる $A,B$ がただ 1 組ある（$A=a_0$、$B=a_1/\alpha-a_0$）。

証明（定理 2.2）

構造。 この漸化式を満たす複素数列全体 $V$ は、項ごとの和とスカラー倍で閉じているので、複素ベクトル空間をなします（ベクトル空間（定義 3.1）［ベクトル空間と線形変換］）。$a\in V$ は最初の 2 項 $(a_0,a_1)$ で一意に決まり（帰納法）、任意の $(a_0,a_1)\in\mathbb{C}^2$ に対して $V$ の元がある（漸化式で項を決める）ので、$a\mapsto(a_0,a_1)$ は線形な全単射、すなわち $V$ は 2 次元です。したがって、$V$ の 2 つの元で初期値の組 $(a_0,a_1)$ が 1 次独立なものを見つければ、それが $V$ の基底になります。

解の候補。 $u_n=\alpha^n$ は漸化式を満たします：$\alpha^{n+2}-p\alpha^{n+1}-q\alpha^n=\alpha^n(\alpha^2-p\alpha-q)=0$。$\beta^n$ も同様です。

$\alpha\ne\beta$ のとき。 $u_n=\alpha^n$、$v_n=\beta^n$ の初期値は $(1,\alpha)$、$(1,\beta)$ で、行列式 $\beta-\alpha\ne0$ なので 1 次独立。基底なので、任意の $a\in V$ は $A\alpha^n+B\beta^n$ と一意に書け、$A,B$ は $n=0,1$ の条件の連立方程式の解です。

$\alpha=\beta$ のとき。 $p=2\alpha$、$q=-\alpha^2$ なので $\alpha\ne0$。$u_n=\alpha^n$ と $w_n=n\alpha^n$ を考えます。$w_{n+2}=(n+2)\alpha^{n+2}$ で、$pw_{n+1}+qw_n=2\alpha(n+1)\alpha^{n+1}-\alpha^2\cdot n\alpha^n=(n+2)\alpha^{n+2}$ より $w\in V$。初期値は $(1,\alpha)$ と $(0,\alpha)$ で、行列式 $\alpha\ne0$ なので 1 次独立、基底になります。

∎

例 2.3（Fibonacci 数の閉じた式）

$F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$。特性方程式 $x^2-x-1=0$ の解は $\phi=\tfrac{1+\sqrt5}2$、$\psi=\tfrac{1-\sqrt5}2$ で相異なる。$A+B=0$、$A\phi+B\psi=1$ から $A=\tfrac1{\phi-\psi}=\tfrac1{\sqrt5}$、$B=-\tfrac1{\sqrt5}$。よって $F_n=\dfrac{\phi^n-\psi^n}{\sqrt5}$（Binet の公式）。$|\psi|<1$ なので $F_n$ は $\phi^n/\sqrt5$ に最も近い整数です。

例 2.4（重解の場合）

$a_{n+2}=4a_{n+1}-4a_n$、$a_0=1$、$a_1=4$。特性方程式 $x^2-4x+4=0$ は重解 $\alpha=2$。$A=1$、$B=4/2-1=1$ から $a_n=(1+n)2^n$。確かめると $a_2=4\cdot4-4\cdot1=12=3\cdot2^2$ ✓。

3. 行列の冪と剰余による計算

行列 $M$ の冪を、素朴に掛け算を繰り返さずに求めたい、という動機の節です。$M^2$ が $M$ と単位行列の組み合わせで書ければ、$M^3,M^4,\dots$ もすべて $M$ と $I$ の組み合わせに押し込めます。その組み合わせの係数を、多項式の割り算の余りで機械的に決めるのが次の定理です。

定理 3.1（行列の冪を多項式の剰余で計算する）✓

$M$ を複素係数の正方行列とし、$M^2-tM+dI=0$（零行列）を満たすとする（$2\times2$ 行列では $t=\operatorname{tr}M$、$d=\det M$ がこれを満たす：ケーリー・ハミルトンの定理（系 7.3）［加群と PID 上の構造定理］。特性多項式は 特性多項式（定義 4.1）［固有値と固有ベクトル］）。多項式 $x^n$ を $\chi(x)=x^2-tx+d$ で割った余りを $u_nx+v_n$ とする（多項式の除法の原理（定理 2.2）［多項式の割り算と高次方程式］）と、

$$M^n=u_nM+v_nI\qquad(n\ge0)$$

である。さらに $u_0=0$、$v_0=1$、$u_{n+1}=tu_n+v_n$、$v_{n+1}=-du_n$。とくに $u_{n+2}=tu_{n+1}-du_n$ で、$\chi$ の解 $\alpha\ne\beta$ に対し $u_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}$ である。

証明（定理 3.1）

$x^n=Q(x)\chi(x)+u_nx+v_n$ に $x=M$ を代入します。$M$ の多項式どうしは積について可換で、和と積は多項式の演算を保つので $M^n=Q(M)\chi(M)+u_nM+v_nI$、そして $\chi(M)=0$ です。

漸化式：$x^{n+1}=x(Q\chi+u_nx+v_n)=xQ\chi+u_nx^2+v_nx$ で、$x^2=\chi+tx-d$ より $u_nx^2+v_nx\equiv(tu_n+v_n)x-du_n\pmod\chi$。余りの一意性（多項式の除法の原理（定理 2.2）［多項式の割り算と高次方程式］）から $u_{n+1}=tu_n+v_n$、$v_{n+1}=-du_n$。消去して $u_{n+2}=tu_{n+1}-du_n$。$\alpha,\beta$ は $\chi$ の解なので $x^n=Q\chi+u_nx+v_n$ に代入して $\alpha^n=u_n\alpha+v_n$、$\beta^n=u_n\beta+v_n$。引くと $u_n=\tfrac{\alpha^n-\beta^n}{\alpha-\beta}$。

∎

命題 3.2（Fibonacci 行列の冪）✓

$F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$ とし、$M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ とする。$n\ge1$ について

$$M^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}.$$

証明（命題 3.2）

$M$ は $t=\operatorname{tr}M=1$、$d=\det M=-1$ で、$\chi=x^2-x-1$。$x^n\equiv F_nx+F_{n-1}\pmod\chi$（$n\ge1$）を帰納法で示します。$n=1$ は $x\equiv F_1x+F_0$。$x^{n+1}\equiv F_nx^2+F_{n-1}x\equiv F_n(x+1)+F_{n-1}x=(F_n+F_{n-1})x+F_n=F_{n+1}x+F_n$（$x^2\equiv x+1$）。定理 3.1 と余りの一意性から $M^n=F_nM+F_{n-1}I=\begin{pmatrix}F_n+F_{n-1}&F_n\\F_n&F_{n-1}\end{pmatrix}$ で、$F_n+F_{n-1}=F_{n+1}$ です。

∎

例 3.3（重解と Jordan 細胞）

$M=\begin{pmatrix}\alpha&1\\0&\alpha\end{pmatrix}$（Jordan 細胞、ジョルダン細胞（定義 6.1）［対角化とジョルダン標準形］、$\alpha\ne0$ とする。$\alpha=0$ なら $M^2=0$ で、$n\ge2$ で $M^n=0$）は $t=2\alpha$、$d=\alpha^2$、$\chi=(x-\alpha)^2$。重解のときも $u_n$ の漸化式は $u_{n+2}=2\alpha u_{n+1}-\alpha^2u_n$、$u_0=0$、$u_1=1$ で、定理 2.2 の重解の場合から $u_n=n\alpha^{n-1}$、$v_n=-\alpha^2u_{n-1}=-(n-1)\alpha^n$。したがって $M^n=n\alpha^{n-1}M-(n-1)\alpha^nI=\begin{pmatrix}\alpha^n&n\alpha^{n-1}\\0&\alpha^n\end{pmatrix}$。重解の漸化式に $n\alpha^n$ が現れる理由は、対角化できない行列（Jordan 細胞）の冪に $n\alpha^{n-1}$ が現れるからです。

命題 3.4（歩道の数と行列の冪）✓

有限な有向グラフ（頂点 $1,\dots,m$、頂点 $i$ から $j$ への辺が $A_{ij}$ 本）の隣接行列を $A$ とする。このとき、頂点 $i$ から $j$ へ長さ $n$ の歩道（辺を $n$ 本順にたどる道）の数は $(A^n)_{ij}$ である。

証明（命題 3.4）

$n$ に関する帰納法。$n=0$ は $A^0=I$（長さ 0 の歩道は $i=j$ のときのみ 1 本）。長さ $n+1$ の歩道は、$i$ から $k$ への長さ $n$ の歩道と、$k$ から $j$ への辺 1 本の組なので、その数は $\sum_k(A^n)_{ik}A_{kj}=(A^{n+1})_{ij}$（行列の積（定義 4.1）［行列と連立一次方程式］）です。

∎

例 3.5（三角形の上の歩道）

3 頂点の完全グラフの隣接行列 $A=J-I$（$J$ は成分がすべて $1$ の行列）は $A^2=J^2-2J+I=3J-2J+I=A+2I$ なので、$t=1$、$d=-2$、$\chi=x^2-x-2=(x-2)(x+1)$。定理 3.1 から $u_n=\tfrac{2^n-(-1)^n}{3}$、$v_n=2u_{n-1}=\tfrac{2^n+2(-1)^n}{3}$。$A$ の対角成分は $0$ なので、頂点 1 から 1 へ戻る長さ $n$ の歩道の数は $(A^n)_{11}=v_n=\tfrac{2^n+2(-1)^n}{3}$。$n=2$ で $2$（$1\to2\to1$、$1\to3\to1$）、$n=3$ で $2$ と確かめられます。

4. 分数型の漸化式

分数の形の漸化式は一見扱いにくいですが、固定点（$a_{n+1}$ と $a_n$ が同じ値になる点）を引くと分子が $a_n-\lambda$ の倍数になり、等比や等差の形にそろいます。次の定理はその整理です。

定理 4.1（分数型漸化式）✓

$p,q,r,s$ を複素数とし、$r\ne0$、$ps-qr\ne0$ とする。数列 $(a_n)$ が $a_{n+1}=\dfrac{pa_n+q}{ra_n+s}$（すべての項で分母が $0$ でない）を満たすとし、$\lambda$ を固定点（$\lambda=\tfrac{p\lambda+q}{r\lambda+s}$、すなわち $r\lambda^2+(s-p)\lambda-q=0$ の解）とする。

1. 異なる 2 つの固定点 $\lambda_1,\lambda_2$ があるとき、$\kappa=\dfrac{p-r\lambda_1}{p-r\lambda_2}$ とすると、$\dfrac{a_{n}-\lambda_1}{a_{n}-\lambda_2}=\kappa^{n}\,\dfrac{a_0-\lambda_1}{a_0-\lambda_2}$（$a_n\ne\lambda_2$）。
2. 固定点が重解 $\lambda$ のとき、$\dfrac1{a_{n+1}-\lambda}=\dfrac1{a_n-\lambda}+\dfrac{r}{p-r\lambda}$（$a_n\ne\lambda$）。すなわち $\dfrac1{a_n-\lambda}$ は等差数列である。

証明（定理 4.1）

$\lambda$ が固定点なら $q-s\lambda=r\lambda^2-p\lambda=-\lambda(p-r\lambda)$ で、

$$a_{n+1}-\lambda=\frac{(p-r\lambda)a_n+q-s\lambda}{ra_n+s}=\frac{(p-r\lambda)(a_n-\lambda)}{ra_n+s}.\tag{$*$}$$

また $p-r\lambda\ne0$ です。$p-r\lambda=0$ なら $q-s\lambda=0$ で、$p=r\lambda$、$q=s\lambda$ から $ps-qr=r\lambda s-s\lambda r=0$ となり仮定に反します。

(1) $(*)$ を $\lambda_1,\lambda_2$ について作って割ると、$\dfrac{a_{n+1}-\lambda_1}{a_{n+1}-\lambda_2}=\kappa\dfrac{a_n-\lambda_1}{a_n-\lambda_2}$ で、等比数列の公式（帰納法）から主張を得ます。 (2) $(*)$ の逆数をとると $\dfrac1{a_{n+1}-\lambda}=\dfrac{ra_n+s}{(p-r\lambda)(a_n-\lambda)}=\dfrac{r(a_n-\lambda)+(r\lambda+s)}{(p-r\lambda)(a_n-\lambda)}=\dfrac r{p-r\lambda}+\dfrac{r\lambda+s}{p-r\lambda}\cdot\dfrac1{a_n-\lambda}$。重解は $\lambda=\tfrac{p-s}{2r}$（判別式 $(s-p)^2+4qr=0$）なので $r\lambda+s=\tfrac{p+s}2=p-r\lambda$ で、第 2 項の係数は $1$ です。

∎

例 4.2（分数型漸化式の例）

$a_0=0$、$a_{n+1}=\dfrac{2a_n+1}{a_n+2}$。固定点は $\lambda^2+(2-2)\lambda-1=0$ から $\lambda=\pm1$。$\kappa=\dfrac{p-r\lambda_1}{p-r\lambda_2}=\dfrac{2-1}{2+1}=\dfrac13$（$\lambda_1=1$、$\lambda_2=-1$、$r=1$、$p=2$）。$\dfrac{a_n-1}{a_n+1}=\dfrac1{3^n}\cdot\dfrac{0-1}{0+1}=-\dfrac1{3^n}$ から $a_n=\dfrac{3^n-1}{3^n+1}$。$a_1=\tfrac12$ と確かめられます。

5. Fibonacci 数の整除性

定理 5.1（Fibonacci 数の最大公約数）✓

$F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$ とする。正の整数 $m,n$ について

$$\gcd(F_m,F_n)=F_{\gcd(m,n)}.$$

証明の方針です。加法公式で $\gcd(F_a,F_b)=\gcd(F_{a-b},F_b)$ を示し、添え字に互除法と同じ引き算を繰り返すと、最後に $F_{\gcd(m,n)}$ が残ります。(c) の整除の議論が核心で、隣り合う項が互いに素であること (b) を使います。

証明（定理 5.1）

(a) 加法公式。 $M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ について $M^{m+n}=M^mM^n$ の $(1,2)$ 成分を 命題 3.2 の形で書くと、$m,n\ge1$ で $F_{m+n}=F_{m+1}F_n+F_mF_{n-1}$。

(b) 隣り合う項は互いに素。 $\gcd(F_{n+1},F_n)=1$ を $n$ に関する帰納法で示します。$\gcd(F_1,F_0)=\gcd(1,0)=1$。$\gcd(F_{n+2},F_{n+1})=\gcd(F_{n+1}+F_n,F_{n+1})=\gcd(F_n,F_{n+1})=1$（$x+y$ と $x$ の公約数は $x$ と $y$ の公約数と同じ）。

(c) 差への還元。 $a>b\ge1$ とし、$c=a-b$ とおく。(a) で $m=c$、$n=b$ とすると $F_a=F_{c+1}F_b+F_cF_{b-1}$ なので、$d=\gcd(F_a,F_b)$ は $F_cF_{b-1}$ と $F_b$ の最大公約数 $\gcd(F_cF_{b-1},F_b)$ に等しい（$F_{c+1}F_b$ は $F_b$ の倍数）。この $d$ は $F_b$ の約数で、(b) により $F_{b-1}$ と互いに素。$d\mid F_{b-1}F_c$ なので、ユークリッドの補題（一般形、ユークリッドの補題（一般形）（補題 2.2）［整除と素因数分解］）により $d\mid F_c$。よって $d\mid\gcd(F_c,F_b)$。逆に $\gcd(F_c,F_b)$ は $F_cF_{b-1}$ と $F_b$ の公約数なので $d$ を割る。ゆえに $\gcd(F_a,F_b)=\gcd(F_{a-b},F_b)$。

(d) 帰納法。 $m+n$ に関する強い帰納法（完全帰納法（定理 4.3）［証明の技術］）。$m=n$ なら両辺 $F_m$。$m>n$ なら (c) と帰納法の仮定より $\gcd(F_m,F_n)=\gcd(F_{m-n},F_n)=F_{\gcd(m-n,n)}=F_{\gcd(m,n)}$（$m-n$ と $n$ の公約数の集合は $m$ と $n$ の公約数の集合に等しい。互除法の原理、互除法の正しさ（定理 3.2）［整除と素因数分解］）。$m<n$ も同じです。

∎

たとえば $\gcd(F_{12},F_{18})=F_6=8$（$F_{12}=144$、$F_{18}=2584$、どちらも $8$ の倍数で、$144/8=18$ と $2584/8=323$ は互いに素）。

6. 母関数と数の代入

定義 6.1（母関数）↗

数列 $(a_n)_{n\ge0}$ に対し、形式的冪級数 $G(x)=\sum_{n\ge0}a_nx^n$（形式的冪級数環（定義 2.1）［数え上げと母関数］）を $(a_n)$ の母関数という。

形式的冪級数では、$x$ に数を代入することはまだ許されていません。代入には収束が必要です。次の定理は、漸化式を満たす数列について、母関数の具体形と代入できる範囲を与えます。

形式的冪級数は係数の列にすぎないので、$x$ に数を入れて値を求めることはできません。実際に数を入れてよいのは、級数が収束するときだけです。次の定理の (2) は、数列の項の大きさを等比数列で押さえて、収束する範囲を具体的に決めます。

定理 6.2（線形漸化式の母関数と代入）✓

$p,q,a_0,a_1$ を実数とし、$(a_n)_{n\ge0}$ が $a_{n+2}=pa_{n+1}+qa_n$ を満たすとする。$Q(x)=1-px-qx^2$ とする。

1. 形式的冪級数環で $Q(x)\,G(x)=a_0+(a_1-pa_0)x$。$Q$ は定数項が $1$ なので逆元をもち（逆元の存在（命題 2.2）［数え上げと母関数］）、$G(x)=\dfrac{a_0+(a_1-pa_0)x}{Q(x)}$。
2. $\rho=|p|+|q|+1$ とする。実数 $x$ が $|x|<1/\rho$ を満たすなら、級数 $\sum_{n\ge0}a_nx^n$ は収束し、その和は $\dfrac{a_0+(a_1-pa_0)x}{1-px-qx^2}$（分母は $0$ でない）に等しい。

証明（定理 6.2）

(1) $Q(x)G(x)$ の $x^n$ の係数は、$n\ge2$ で $a_n-pa_{n-1}-qa_{n-2}=0$、$n=0$ で $a_0$、$n=1$ で $a_1-pa_0$ です。

(2) まず $|a_n|\le C\rho^n$（$C=\max(|a_0|,|a_1|/\rho)$）を帰納法で示します。$n=0,1$ は定義どおり。$n\to n+2$：$|a_{n+2}|\le|p|C\rho^{n+1}+|q|C\rho^n=C\rho^n(|p|\rho+|q|)$ で、$\rho^2-|p|\rho-|q|=\rho(\rho-|p|)-|q|\ge\rho-|q|\ge1>0$（$\rho-|p|=|q|+1\ge1$）なので $|p|\rho+|q|\le\rho^2$。したがって $|a_n x^n|\le C(\rho|x|)^n$ で、$\rho|x|<1$ なので等比級数（等比級数（命題 6.2）［数とは何か］）との比較判定法（比較判定法（定理 4.2）［級数と収束判定］）により $\sum|a_nx^n|$ は収束し、絶対収束すれば収束します（絶対収束すれば収束する（定理 7.2）［級数と収束判定］）。$G(x)=\sum a_nx^n$ とおきます。

$S_N=\sum_{n=0}^Na_nx^n$ に $Q(x)$ をかけて項を整理すると（$2\le m\le N$ の係数は $a_m-pa_{m-1}-qa_{m-2}=0$）

$$Q(x)S_N=a_0+(a_1-pa_0)x-(pa_N+qa_{N-1})x^{N+1}-qa_Nx^{N+2}.$$

$N\to\infty$ で、$|a_Nx^N|\le C(\rho|x|)^N\to0$ なので、最後の 2 項は $0$ に収束し、$S_N\to G(x)$ なので $Q(x)G(x)=a_0+(a_1-pa_0)x$ です。$|px+qx^2|\le|p||x|+|q||x|^2<\tfrac{|p|+|q|}\rho<1$（$|x|<1/\rho<1$）なので $|Q(x)|\ge1-|px+qx^2|>0$。割れば主張を得ます。

∎

例 6.3（Fibonacci 数の母関数）

$a_0=0$、$a_1=1$、$p=q=1$ で $G(x)=\dfrac{x}{1-x-x^2}$。$1-x-x^2=(1-\phi x)(1-\psi x)$（$\phi+\psi=1$、$\phi\psi=-1$）なので部分分数分解 $\dfrac{x}{1-x-x^2}=\dfrac1{\sqrt5}\Bigl(\dfrac1{1-\phi x}-\dfrac1{1-\psi x}\Bigr)$ から、$x^n$ の係数は $\tfrac{\phi^n-\psi^n}{\sqrt5}=F_n$（Binet の公式を別の道で得た）。代入の例：$|x|<\tfrac13$ に含まれる $x=\tfrac1{10}$ で $\sum_{n\ge0}\dfrac{F_n}{10^n}=\dfrac{0.1}{1-0.1-0.01}=\dfrac{10}{89}\approx0.11236$。実際 $0.1+0.01+0.002+0.0003+0.00005+0.000008+\cdots$ です。

7. 分割数の母関数：Euler の分割恒等式

正の整数 $n$ の分割とは、和が $n$ となる正の整数の（順序を区別しない）組のことです。$n=0$ の分割は空の組 1 個とします。$n$ の分割のうち、すべての部分が奇数のものの個数を $p_{\mathrm{odd}}(n)$、すべての部分が相異なるものの個数を $p_{\mathrm{dist}}(n)$ とします。たとえば $n=6$ の相異なる部分への分割は $6,\ 5+1,\ 4+2,\ 3+2+1$ の 4 個、奇数の部分への分割は $5+1,\ 3+3,\ 3+1+1+1,\ 1+1+1+1+1+1$ の 4 個で一致します。

定理 7.1（Euler の分割恒等式）✓

すべての整数 $n\ge0$ について $p_{\mathrm{odd}}(n)=p_{\mathrm{dist}}(n)$。

証明の方針です。両辺の母関数を、積の形でそれぞれ書きます。「$x^{N+1}$ を法とする」とは、$x^{N+1}$ 以上の項を無視して、$x^N$ までの係数だけを比べる、という意味です。比べたい $x^n$（$n\le N$）の係数はこれで失われません。

証明（定理 7.1）

$N\ge n$ を固定し、形式的冪級数環（形式的冪級数環（定義 2.1）［数え上げと母関数］）で $x^{N+1}$ を法とする合同式（係数が $x^{N}$ まで一致する）を考えます。$1-x^k$ は定数項が $1$ なので逆元 $\sum_{m\ge0}x^{km}$ をもちます（逆元の存在（命題 2.2）［数え上げと母関数］）。

(a) $\prod_{k=1}^N(1+x^k)=\sum_{S\subseteq\{1,\dots,N\}}x^{\sum S}$ の $x^n$ の係数は、和が $n$ の部分集合の個数、すなわち相異なる部分への分割の数で、$n\le N$ なので $p_{\mathrm{dist}}(n)$。

(b) $\prod_{k\le N,\ k\text{ 奇数}}\dfrac1{1-x^k}=\sum_{(m_k)}x^{\sum km_k}$ の $x^n$ の係数は、$\sum km_k=n$ となる非負整数の組 $(m_k)$（奇数 $k$ をちょうど $m_k$ 回使う）の個数で、$p_{\mathrm{odd}}(n)$（$n\le N$ なので奇数の部分は $N$ 以下）。

(c) $(1+x^k)(1-x^k)=1-x^{2k}$ なので、$\prod_{k=1}^N(1+x^k)=\prod_{k=1}^N\dfrac{1-x^{2k}}{1-x^k}$。分母のうち $k$ 偶数の部分 $\prod_{j\le N/2}(1-x^{2j})$ は分子 $\prod_{k\le N}(1-x^{2k})$ の一部と打ち消しあい、

$$\prod_{k=1}^N(1+x^k)=\frac{\prod_{N/2<j\le N}(1-x^{2j})}{\prod_{k\le N,\ k\text{ 奇数}}(1-x^k)}.$$

分子の各因子で $2j\ge N+1$ なので $1-x^{2j}\equiv1\pmod{x^{N+1}}$。したがって $\prod_{k=1}^N(1+x^k)\equiv\prod_{k\text{ 奇数}\le N}\dfrac1{1-x^k}\pmod{x^{N+1}}$。

(a)(b)(c) から、$x^n$（$n\le N$）の係数を比べて $p_{\mathrm{dist}}(n)=p_{\mathrm{odd}}(n)$ です。

∎

注意 7.2（五角数）

$k(3k-1)/2$（$k=1,2,3,4,\dots$）の形の数 $1,5,12,22,\dots$ を五角数といいます（$k$ 個の点を一辺にもつ正五角形状に並べた点の個数）。無限積 $\prod_{k\ge1}(1-x^k)$ を展開すると、係数が $\pm1$ と $0$ だけで、$\pm1$ が現れる指数がちょうど（一般化された）五角数になる、という Euler の五角数定理があります。分割数の漸化式を導くのに使われます。この記事の他の議論は、この定理を使いません。興味のある読者は、G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1976 の第 1 章を読んでください。

8. 大学ではどこへ続くか

漸化式の特性方程式は、常微分方程式（ode）の定数係数線形方程式の離散版で、$\alpha^n$ が $e^{\alpha t}$ に、重解の $n\alpha^n$ が $te^{\alpha t}$ に対応します。解空間が 2 次元であることは、線形代数（linear-algebra）の次元の議論の最初の例です。行列の冪 $M^n$ の剰余による計算は、$M$ の最小多項式・Cayley–Hamilton の定理（algebra）の応用で、対角化できない場合は Jordan 標準形に至ります。母関数は組合せ論（combinatorics）で数え上げの道具として一般化され、$x$ に数を代入できる範囲は複素解析の収束半径の理論になります。Euler の分割恒等式は、$q$-級数と分割理論の出発点です。

9. 演習

演習 9.1易

$a_0=1$、$a_{n+1}=3a_n-4$ の一般項を求めよ。

解答

$p=3$、$q=-4$、固定点 $c=\tfrac{-4}{1-3}=2$。定理 2.1 により $a_n=3^n(1-2)+2=2-3^n$。$a_1=3-4=-1=2-3$ で一致します。

演習 9.2標準

$a_0=1$、$a_1=3$、$a_{n+2}=5a_{n+1}-6a_n$ の一般項を求めよ。

解答

特性方程式 $x^2-5x+6=0$ の解は $2,3$。定理 2.2 により $a_n=A2^n+B3^n$、$A+B=1$、$2A+3B=3$ より $B=1$、$A=0$。よって $a_n=3^n$。$a_2=15-6=9$ で一致。

演習 9.3標準

$M=\begin{pmatrix}3&-1\\1&1\end{pmatrix}$ の $n$ 乗 $M^n$ を求めよ。

解答

$t=4$、$d=4$、$\chi=(x-2)^2$（重解 $\alpha=2$）。定理 3.1 と 例 3.3 の計算と同様に、$u_n=n2^{n-1}$、$v_n=-4u_{n-1}=-(n-1)2^n$。$M^n=u_nM+v_nI=2^{n-1}\begin{pmatrix}n+2&-n\\n&2-n\end{pmatrix}$。$n=2$ で $\begin{pmatrix}8&-4\\4&0\end{pmatrix}$ となり、$M^2$ の直接計算と一致します。

演習 9.4易

$n=7$ について、相異なる部分への分割と奇数の部分への分割をすべて書き出し、定理 7.1 を確かめよ。

解答

相異なる部分：$7,\ 6+1,\ 5+2,\ 4+3,\ 4+2+1$ の 5 個。奇数の部分：$7,\ 5+1+1,\ 3+3+1,\ 3+1+1+1+1,\ 1+1+1+1+1+1+1$ の 5 個。一致します。

参考文献

• Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994 — Chapter 1・2（漸化式と和）、Chapter 7（母関数）。
• Herbert S. Wilf, generatingfunctionology, 3rd ed., A K Peters, 2006 — Chapter 1。
• George E. Andrews, The Theory of Partitions, Cambridge University Press, 1976 — Chapter 1。
• 杉浦光夫『解析入門 I』東京大学出版会、1980 — 級数に関する節。