# 漸化式と母関数：特性方程式・行列の冪・Fibonacci 数・分割数 > 1 次・2 次の線形漸化式を特性方程式で解き、行列の冪を剰余で計算し、分数型漸化式を固定点で直す。Fibonacci 数の整除性、母関数への数の代入、Euler の分割恒等式を証明つきで導く。 > https://rikai.mugen-giken.com/mathematics/hs-algebra/recurrences-generating-functions ## 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. 動機：漸化式の「解」とは何か 漸化式 $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. **[ベクトル空間](/mathematics/linear-algebra/vector-spaces#def-vector-space)として**：漸化式を満たす数列全体は 2 次元のベクトル空間で、$\alpha^n$ と $\beta^n$ はその基底になる。 2. **行列として**：漸化式は 2 次の行列の冪 $M^n$ の計算で、$M^n$ は $x^n$ を特性多項式で割った余りで書ける。 3. **母関数として**：数列 $(a_n)$ を冪級数 $\sum a_nx^n$ に写すと、漸化式は多項式の掛け算になり、解は有理関数として一目でわかる。 使う道具は前の章の、多項式の除法の原理（）、複素数係数の 2 次方程式（）、数列の和と差分（[数列](/mathematics/hs-algebra/sequences)）です。この記事では、項番号を $0$ から始める数列 $(a_n)_{n\ge0}$ も使います。 ## 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. $$ $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 つ見つかれば全部の解が書ける」ということです。 $p,q$ を複素数、$q\ne0$ とし、数列 $(a_n)_{n\ge0}$ が $a_{n+2}=pa_{n+1}+qa_n$ を満たすとする。**特性方程式** $x^2-px-q=0$ の 2 解を $\alpha,\beta$ とする（）。 - $\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$）。 **構造。** この漸化式を満たす複素数列全体 $V$ は、項ごとの和とスカラー倍で閉じているので、複素ベクトル空間をなします（）。$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 次独立、基底になります。 $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$ に最も近い整数です。 $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$ の組み合わせに押し込めます。その組み合わせの係数を、多項式の割り算の余りで機械的に決めるのが次の定理です。 $M$ を複素係数の正方行列とし、$M^2-tM+dI=0$（零行列）を満たすとする（$2\times2$ 行列では $t=\operatorname{tr}M$、$d=\det M$ がこれを満たす：。特性多項式は ）。多項式 $x^n$ を $\chi(x)=x^2-tx+d$ で割った余りを $u_nx+v_n$ とする（）と、 $$ 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}$ である。 $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$。余りの一意性（）から $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}$。 $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}. $$ $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$）。 と余りの一意性から $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}$ です。 $M=\begin{pmatrix}\alpha&1\\0&\alpha\end{pmatrix}$（Jordan 細胞、、$\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$ で、 の重解の場合から $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}$ が現れるからです。 有限な有向グラフ（頂点 $1,\dots,m$、頂点 $i$ から $j$ への辺が $A_{ij}$ 本）の隣接行列を $A$ とする。このとき、頂点 $i$ から $j$ へ長さ $n$ の歩道（辺を $n$ 本順にたどる道）の数は $(A^n)_{ij}$ である。 $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}$（）です。 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)$。 から $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$ の倍数になり、等比や等差の形にそろいます。次の定理はその整理です。 $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}$ は等差数列である。 $\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$ です。 $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 数の整除性 $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) を使います。 **(a) 加法公式。** $M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ について $M^{m+n}=M^mM^n$ の $(1,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$ なので、ユークリッドの補題（一般形、）により $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$ に関する強い帰納法（）。$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$ の公約数の集合に等しい。互除法の原理、）。$m たとえば $\gcd(F_{12},F_{18})=F_6=8$（$F_{12}=144$、$F_{18}=2584$、どちらも $8$ の倍数で、$144/8=18$ と $2584/8=323$ は互いに素）。 ## 6. 母関数と数の代入 数列 $(a_n)_{n\ge0}$ に対し、形式的冪級数 $G(x)=\sum_{n\ge0}a_nx^n$（）を $(a_n)$ の**母関数**という。 形式的冪級数では、$x$ に数を代入することは**まだ許されていません**。代入には収束が必要です。次の定理は、漸化式を満たす数列について、母関数の具体形と代入できる範囲を与えます。 形式的冪級数は係数の列にすぎないので、$x$ に数を入れて値を求めることはできません。実際に数を入れてよいのは、級数が収束するときだけです。次の定理の (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$ なので逆元をもち（）、$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$ でない）に等しい。 **(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$ なので等比級数（）との比較判定法（）により $\sum|a_nx^n|$ は収束し、絶対収束すれば収束します（）。$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$。割れば主張を得ます。 $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 個で一致します。 すべての整数 $n\ge0$ について $p_{\mathrm{odd}}(n)=p_{\mathrm{dist}}(n)$。 証明の方針です。両辺の母関数を、積の形でそれぞれ書きます。「$x^{N+1}$ を法とする」とは、$x^{N+1}$ 以上の項を無視して、$x^N$ までの係数だけを比べる、という意味です。比べたい $x^n$（$n\le N$）の係数はこれで失われません。 $N\ge n$ を固定し、形式的冪級数環（）で $x^{N+1}$ を法とする合同式（係数が $x^{N}$ まで一致する）を考えます。$1-x^k$ は定数項が $1$ なので逆元 $\sum_{m\ge0}x^{km}$ をもちます（）。 **(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 $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. 演習 $a_0=1$、$a_{n+1}=3a_n-4$ の一般項を求めよ。 $p=3$、$q=-4$、固定点 $c=\tfrac{-4}{1-3}=2$。 により $a_n=3^n(1-2)+2=2-3^n$。$a_1=3-4=-1=2-3$ で一致します。 $a_0=1$、$a_1=3$、$a_{n+2}=5a_{n+1}-6a_n$ の一般項を求めよ。 特性方程式 $x^2-5x+6=0$ の解は $2,3$。 により $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$ で一致。 $M=\begin{pmatrix}3&-1\\1&1\end{pmatrix}$ の $n$ 乗 $M^n$ を求めよ。 $t=4$、$d=4$、$\chi=(x-2)^2$（重解 $\alpha=2$）。 と の計算と同様に、$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$ の直接計算と一致します。 $n=7$ について、相異なる部分への分割と奇数の部分への分割をすべて書き出し、 を確かめよ。 相異なる部分：$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 — 級数に関する節。