漸化式と数え上げ ― 線形漸化式の解法

特性方程式による線形漸化式の求解法，非同次の特殊解，母関数との等価性，格子経路の漸化式，行列累乗とkitamasa法を解説する．

2026年2月27日

1 定数係数線形漸化式

定義 1 (定数係数線形漸化式).

数列

(a_{n})_{n \geq 0}

が $d$ 次定数係数同次線形漸化式を満たすとは，定数

c_{1}, \dots, c_{d}

（

c_{d} \neq = 0

）が存在して

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{d} a_{n - d} (n \geq d)

が成り立つことをいう．

定義 2 (特性方程式).

上記の漸化式に対して，方程式

t^{d} - c_{1} t^{d - 1} - c_{2} t^{d - 2} - \dots - c_{d} = 0

を特性方程式（characteristic equation）という．

2 相異なる根の場合

定理 3.

特性方程式が

d

個の相異なる根

r_{1}, r_{2}, \dots, r_{d}

を持つとき，漸化式の一般解は

a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n} + \dots + α_{d} r_{d}^{n}

で与えられる．ここで

α_{1}, \dots, α_{d}

は初期条件から定まる定数である．

証明.

a_{n} = r^{n}

が漸化式の解であるための条件は

r^{n} = c_{1} r^{n - 1} + \dots + c_{d} r^{n - d}

，すなわち

r^{d} = c_{1} r^{d - 1} + \dots + c_{d}

であり，これは特性方程式に他ならない．漸化式は線形であるから解の線形結合も解であり，

d

個の自由な定数を持つ一般解が得られる．

d

個の初期条件から

α_{1}, \dots, α_{d}

が一意に定まることは，ヴァンデルモンド行列式

\prod_{i < j} (r_{j} - r_{i}) \neq = 0

から従う． □

3 重根の場合

定理 4.

特性方程式の根

r

が

m

重根であるとき，

r^{n}, n r^{n}, n^{2} r^{n}, \dots, n^{m - 1} r^{n}

がすべて漸化式の解である．

証明.

形式的べき級数の OGF による証明が簡明である．特性多項式を

p (t) = (t - r)^{m} q (t)

と書くと，

A (x) = g (x) / p (1/ x) x^{d}

の部分分数分解において

(1 - r x)^{- m}

の項が現れる．

[x^{n}] (1 - r x)^{- j} = (j - 1 n + j - 1) r^{n}

は

n

の

j - 1

次多項式に

r^{n}

を掛けた形であり，

j = 1, \dots, m

に対応する解が

n^{j - 1} r^{n}

のスカラー倍で表される． □

4 非同次漸化式

定義 5 (非同次線形漸化式).

a_{n} = c_{1} a_{n - 1} + \dots + c_{d} a_{n - d} + f (n)

の形の漸化式を非同次という．

f (n)

を非同次項という．

定理 6.

非同次漸化式の一般解は「同次漸化式の一般解

+

特殊解1つ」で与えられる．

証明.

非同次漸化式の2つの解

a_{n}, a_{n}^{'}

の差

a_{n} - a_{n}^{'}

は同次漸化式を満たす．よって非同次の任意の解は「特殊解

+

同次解」の形である． □

例 7.

a_{n} = 2 a_{n - 1} + 3^{n}

（

a_{0} = 1

）を解く．特性方程式

t - 2 = 0

より同次解は

α \cdot 2^{n}

．特殊解を

a_{n} = C \cdot 3^{n}

とおくと

C \cdot 3^{n} = 2 C \cdot 3^{n - 1} + 3^{n}

より

C (3 - 2) = 3

，

C = 3

．一般解は

a_{n} = α \cdot 2^{n} + 3^{n + 1}

．

a_{0} = 1

より

α + 3 = 1

，

α = - 2

．答え：

a_{n} = - 2^{n + 1} + 3^{n + 1}

．

5 母関数との等価性

注意 8.

d

次定数係数線形漸化式を満たす数列の OGF は

A (x) = P (x) / Q (x)

の形の有理関数であり，

Q (x)

の次数は

d

，

P (x)

の次数は

d - 1

以下である．逆に，有理関数の形の OGF を持つ数列は定数係数線形漸化式を満たす．部分分数分解と特性方程式による解法は，異なる観点からの同一の操作である．

6 行列累乗

定理 9.

d

次定数係数線形漸化式

a_{n} = c_{1} a_{n - 1} + \dots + c_{d} a_{n - d}

の

n

項目は，

d \times d

行列の

n

乗を用いて

a_{n} a_{n - 1} ⋮ a_{n - d + 1} = c_{1} 10 ⋮ 0 c_{2} 010 \dots \dots \dots ⋱ \dots c_{d - 1} 001 c_{d} 00 ⋮ 0^{n - d + 1} a_{d - 1} a_{d - 2} ⋮ a_{0}

と計算できる．

証明.

漸化式をベクトルの遷移として書き直せば明らかである．行列を

M

と書くと

v_{n} = M v_{n - 1} = M^{n - d + 1} v_{d - 1}

． □

注意 10 (行列累乗の計算量).

M^{n}

は繰り返し二乗法により

O (d^{3} lo g n)

で計算できる．

d

が小さく

n

が非常に大きい場合に有効である．

注意 11 (kitamasa 法).

kitamasa 法は，

d

次線形漸化式の

a_{n}

を

O (d^{2} lo g n)

または FFT を用いて

O (d lo g d lo g n)

で計算する手法である．基本的なアイデアは，

x^{n} mod p (x)

（

p (x)

は特性多項式）を繰り返し二乗法で計算し，

a_{n}

を

a_{0}, \dots, a_{d - 1}

の線形結合として表すことである．

漸化式と数え上げ ― 線形漸化式の解法

1 定数係数線形漸化式

2 相異なる根の場合

3 重根の場合

4 非同次漸化式

5 母関数との等価性

6 行列累乗

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ