漸化式の数理 - 微分方程式との類似から

先日 Fibonacci 数列の一般項を計算する記事を書いたのですが，それに関連して $M$ 項間（線形）漸化式の解き方について，初等微分方程式論と完全にパラレルになるよう解説してみます．
おそらくプログラミングにはまったく役立ちません．（なぜなら，特性方程式が代数的に解けるとは限らないので．）

次の $M$ 項間漸化式を解く，というタスクを考えます：

$$\begin{cases} x_n = a_n, & (0 \leqslant n \leqslant M - 2), \\ \displaystyle x_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i x_{n + i} + c, & (n \geqslant 0). \end{cases}$$

ここで，$a_0, \dotsc, a_{M - 2} \in \mathbb{C}$ は与えられた初期値で，$c, \lambda_0, \dotsc, \lambda_{M - 2} \in \mathbb{C}$ は漸化式の係数です．もちろん $\lambda_0 \neq 0$ を仮定します．（$\lambda_0 = 0$ なら $M - 1$ 項間漸化式になってしまうので．）

$M = 1$ のときは自明な漸化式 $x_n = c$ となり面白くないので，以下 $M \geqslant 2$ とします．（大半の議論は $M = 1$ でも成り立ちます．）

簡単のため，（初期条件を無視した）漸化式 $x_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i x_{n + i} + c$ を (RE) と呼び（recurrence equation），(RE) からさらに定数項 $c$ を除いたもの $x_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i x_{n + i}$ を (RE-h) と呼びましょう（homogeneous）．
この (RE) の解き方は $M$ 階常微分方程式と同じです：

1. (RE-h) の解（斉次解）のうち，線形独立なもの $M$ 個を探す；
2. (RE) の解（特解）を一つ見つける；
3. 「斉次解の線型結合と特解の和」のうち，初期条件を満たすものが求める解である．

以下では複素数体 $\mathbb{C}$ 上で考えますが，一般の体（と特性多項式の分解体）上でも同じ議論が成立します．

（注：正標数の体にも拡張することを念頭に置いているので，議論がやや冗長な部分もあります．）

解の線形性

この (RE-h) の解全体のなす集合（解空間）

$$X := \left\{ (x_n)_{n = 0}^\infty \subset \mathbb{C} \mid \text{satisfies (RE-h)} \right\}$$

は $\mathbb{C}$ 上のベクトル空間となります．すなわち，$(x_n)_n, (y_n)_n \in X$ を (RE-h) の解，$\lambda \in \mathbb{C}$ をスカラーとしたとき，$(x_n + y_n)_n, (\lambda x_n)_n$ もまた (RE-h) の解となります．

このベクトル空間 $X$ は，より大きなベクトル空間

$$S := \mathrm{Map} (\mathbb{Z}_{\geqslant 0}, \mathbb{C}) = \left\{ (x_n)_{n = 0}^\infty \subset \mathbb{C} \right\}$$

の部分空間となっています．

差分演算子

この空間 $S$ における線形独立性を調べるために，まず差分演算子というものを導入します．

差分演算子とは，次の式で定まる $S$ 上の線形作用素 $p : S \to S$ のことです：

$$p x_\bullet = x_\bullet [1] - x_\bullet \quad (x_\bullet = (x_n)_n \in S).$$

ただし，一般に整数 $k \in \mathbb{Z}$ に対し，数列 $x_\bullet = (x_n)_n \in S$ の $k$ シフト $x_\bullet [k] \in S$ が $(x_\bullet [k])_n = x_{n + k}$ で定義されます．

言い換えれば，差分演算子とは $(p x_\bullet)_n = x_{n + 1} - x_n$ のことです．
あるいは，$x_{n + 1} = (p x_\bullet)_n + x_n$ であるとも言えます．

つまり $x_\bullet [1] = (p + 1) x_\bullet$ が成り立つ（$1 \in \mathrm{End}_{\mathbb{C}} (S)$ は恒等作用素を表す）ので，一般に $x_\bullet [k] = (p + 1)^k x_\bullet$ となります．

（注：$p$ という記号は，物理学の運動量演算子を元にしています．もちろん，$p$ でなく $D$ でも構いません．）

続いて，$q$ という線形作用素を，

$$(q x_\bullet)_n = n x_n \quad (x_\bullet \in S)$$

で定義します．（$q$ という記号も，やはり物理学の座標演算子が元になっています．）

一般に，多項式 $P (t) = \sum a_i t^i \in \mathbb{C} [t]$ に対して，$P (q)$ という線形作用素を $P (q) = \sum a_i q^i$ で定義します．つまり

$$(P (q) x_\bullet)_n = \left( \sum a_i n^i \right) x_n$$

となっています．ただし，$(q^0 x_\bullet)_n = n^0 x_n$ が成り立つように，便宜上 $0^0 = 1$ としておきましょう．

差分演算子の固有値

さて，零でない複素数 $\psi \in \mathbb{C}^\times = \mathbb{C} \setminus \{ 0 \}$ に対して，その冪列 $\psi^\bullet = (\psi^n)_n \in S$ を考えましょう．

簡単に分かるように

$$(p \psi^\bullet)_n = \psi^{n + 1} - \psi^n = (\psi - 1) \psi^n$$

なので，$\psi^\bullet$ は $p$ の固有値 $\psi - 1$ に属する固有ベクトルとなります．

より一般に，零でない任意の多項式 $0 \neq P (t) \in \mathbb{C} [t]$ に対して $P (q) \psi^\bullet$ は固有値 $\psi - 1$ の一般固有ベクトルであり，$(p - \psi + 1)^{\deg P + 1} P (q) \psi^\bullet = 0$ が成り立ちます．

そのことを $d = \deg P$ に関する帰納法で確かめてみましょう．

$d = 0$ のときは $P (t) = \mathrm{const}$ なので，すでに確認したとおりです．

$d - 1$ 次以下の多項式に対して主張が成立したと仮定します．このとき $P (t) = t^d$ に対して $(p - \psi + 1)^{d + 1} q^d \psi^\bullet = 0$ を示せば十分ですね．

今

$$\left( p q^d \psi^\bullet \right)_n = (n + 1)^d \psi^{n + 1} - n^d \psi^n = \left( \psi (n + 1)^d - n^d \right) \psi^n$$

が成り立つので，

$$\left( (p - \psi + 1) q^d \psi^\bullet \right)_n = \psi \left( (n + 1)^d - n^d \right) \psi^n = \left( Q (q) \psi^\bullet \right)_n$$

となります．ただし，$Q (t) := \psi ((t + 1)^d - t^d) \in \mathbb{C} [t]$ と置きました．

$Q (t)$ は $d - 1$ 次（以下）の多項式なので $(p - \psi + 1)^d Q (q) \psi^\bullet = 0$ であり，結局 $(p - \psi + 1)^{d + 1} q^d \psi^\bullet = 0$ を得ます．

冪の線形独立性

線形代数でよく知られたように，異なる固有値に属する一般固有ベクトルは線形独立です．
つまり，任意の相異なる複素数 $\psi_1, \dotsc, \psi_m \in \mathbb{C}^\times$ と任意の多項式 $P_1 (t), \dotsc, P_m (t) \in \mathbb{C} [t] \setminus \{ 0 \}$ に対して，$\{ P_1 (q) \psi_1^\bullet, \dotsc, P_m (q) \psi_m^\bullet \} \subset S$ は線形独立となります．

さらに，複素数 $\psi \in \mathbb{C}^\times$ に対して，$\{ \psi^\bullet, q \psi^\bullet, \dotsc, q^d \psi^\bullet, \dotsc \} \subset S$ もまた線形独立です．

それを示すために，まずこれらの線型結合が零であるとします：

$$\sum_{i = 0}^{d - 1} \lambda_i q^i \psi^\bullet = 0.$$

このとき任意の $n \geqslant 0$ に対して $\sum \lambda_i n^i \psi^n = 0$ が成り立つので，両辺を $\psi^n$ で割って $\sum \lambda_i n^i = 0$ となります．

また，$0 \leqslant n \leqslant d - 1$ のみを見ることで，$(\lambda_0, \dotsc, \lambda_{d - 1})$ に関する連立方程式

$$\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 1 & 1 & \cdots & 1 \\ \vdots & \vdots & & \vdots \\ 1 & d - 1 & \cdots & (d - 1)^{d - 1} \end{pmatrix} \begin{pmatrix} \lambda_0 \\ \vdots \\ \lambda_{d - 1} \end{pmatrix} = 0$$

を得ます．左辺の行列の行列式は Vandermonde の行列式なので，$\neq 0$．従って $\lambda_0 = \dotsb = \lambda_{d - 1} = 0$ となり，$\{ \psi^\bullet, q \psi^\bullet, \dotsc \}$ の線形独立性が分かりました．

以上の議論より，

$$\left\{ q^d \psi^\bullet \,\middle|\, d \in \mathbb{Z}_{\geqslant 0}, \ \psi \in \mathbb{C}^\times \right\} \subset S$$

は線形独立となります．

斉次解空間の次元

微分方程式の場合と同じように，漸化式 (RE-h) の解空間 $X$ の次元は $M - 1$ となります．
このことを確かめましょう．

次の写像を考えます：

$$\mathbb{C}^{M - 1} \ni a = (a_i) \mapsto x (a)_\bullet \in X.$$

ただし，$x (a)_\bullet$ は，$x_i = a_i$ を初期値とするような (RE-h) の解を表します．このような解が（ただ一つ）存在することは明らかなので，上の写像は線形同型となります．

解の構成

一般斉次解

上の議論より，もし (RE-h) の線形独立な解 $x_\bullet^1, \dotsc, x_\bullet^{M - 1} \in X$ が見つかれば，$(x_\bullet^1, \dotsc, x_\bullet^{M - 1})$ が $X$ の基底となるので，(RE-h) の任意の解はその線型結合 $\sum C_i x_\bullet^i$ で書けます．
そして初期条件 $x_n = a_n$ から係数 $C_n$ を求めれば，最終的な解も分かります．

最も重要なのは，この線形独立な $M - 1$ 個の解を見つける作業です．
とは言っても，やはり線形常微分方程式と同じです．

ここでは特性方程式を用いた解法でいきましょう．

漸化式 (RE-h)

$$x_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i x_{n + i}$$

の特性多項式（characteristic polynomial）$\chi (t) \in \mathbb{C} [t]$ を，$\chi (t) = t^{M - 1} - \sum_{i = 0}^{M - 2} \lambda_i t^i$ で定義します．特性方程式とは $\chi (t) = 0$ という方程式のことです．

さて，(RE-h) を，数列のシフトを用いて

$$x_\bullet [M - 1] = \sum \lambda_i x_\bullet [i]$$

と書き直してみましょう．上述したように $x_\bullet [k] = (p + 1)^k x_\bullet$ でしたから，(RE-h) は

$$(p + 1)^{M - 1} x_\bullet = \sum \lambda_i (p + 1)^i x_\bullet$$

と書けます．これは $\chi (p + 1) x_\bullet = 0$ に他なりませんね．

特性多項式の（相異なる）根を $\psi_1, \dotsc, \psi_\ell \in \mathbb{C}^\times$ として（$\lambda_0 \neq 0$ なので $\chi (t)$ は $0$ を根に持ちません），それぞれの重複度を $m_1, \dotsc, m_\ell$ とします：

$$\chi (t) = (t - \psi_1)^{m_1} \dotsm (t - \psi_\ell)^{m_\ell}.$$

このとき，$m_i - 1$ 次以下の任意の多項式 $P (t) \in \mathbb{C} [t]$ に対して，$P (q) \psi_i^\bullet \in S$ は (RE-h) の解となります．
実際，このような $P (t)$ に対して $(p - \psi_i + 1)^{m_i} P (q) \psi_i^\bullet = 0$ であることは既に示したので，

$$\chi (p + 1) P (q) \psi_i^\bullet = \left( \prod_{j \neq i} (p - \psi_j + 1)^{m_j} \right) (p - \psi_i + 1)^{m_i} P (q) \psi_i \bullet = 0.$$

これによって (RE-h) の解が $M - 1$ 個手に入りました：

$$\left\{ q^d \psi_i^\bullet \,\middle|\, 1 \leqslant i \leqslant \ell, \ 0 \leqslant d \leqslant m_i - 1 \right\}.$$

既に見たようにこれらは線形独立なので，$X$ の基底を成します．

従って，(RE-h) の一般解は $\sum C_{i, d} q^d \psi_i^\bullet$ という形で書くことができます（$C_{i, d} \in \mathbb{C}$）．

(RE) の一般解

なんらかの方法で (RE) の特解（particular solution）$\pi_\bullet \in S$ を一つ求められたとしましょう．
たとえば，もし $1 - \sum \lambda_i \neq 0$ なら

$$\pi_n = \frac{c}{1 - \sum \lambda_i}$$

という定数列が特解となります．

容易に分かるように，(RE-h) の任意の解 $x_\bullet \in X$ に対して，$\pi_\bullet + x_\bullet$ は (RE) の解となります．逆に，(RE) の任意の解 $y_\bullet$ は $y_\bullet - \pi_\bullet \in X$ を満たします．

よって，(RE) の一般解は $\pi_\bullet + \sum C_{i, d} q^d \psi_i^\bullet$ となります．

あとは，与えられた初期値 $(a_0, \dotsc, a_{M - 2}) \in \mathbb{C}^{M - 1}$ に対して，$\pi_n + \sum C_{i, d} q^d \psi_i^n = a_n$ となるように定数 $C_{i, d}$ を求めれば終わりです．

さらなる一般化へ……

以上の話を，微分方程式論を参考にして一般化してみると，次のような感じでしょうか：

• 非線形項を加える — $x_{n + 1} = 1/x_n$ など；
• 変数の数を増やす — $x_n$ から $x_{n, m, \dotsc, \ell}$；
• ベクトル値にする — $x_n \in \mathbb{C}$ から $x_n \in \mathbb{C}^N$；
• Weyl 代数の類似を作る — $p$，$q$ で生成される代数が連接なら、「佐藤の哲学」が活きる；
• 層や多様体に相当する概念を定義し，その上で差分演算子を考える；
• etc.

最後の方針は，有理整数環 $\mathbb{Z}$ 自身は特に面白い幾何構造を持たないので，微妙かもしれません．

代数畑の人間なので，関数解析的な方面への一般化はあまり分かりません……．

いずれにせよ，これらの一般化に関して面白い話題が見つかれば，また記事を書こうと思います．