前回，微分方程式論の観点から漸化式を捉え直したのですが，今回は別の観点 — 母関数を使って定式化しようと思います．
前回の記事で定義した記号を流用しますが，この記事で self-contained にはなっています．
（今回の議論は標数 0 の一般の体（と特性多項式の分解体）で成り立ちます．標数が p > 0 だと \partial^p = 0 となってしまい，少し面倒です．）
母関数とは
母関数という言葉が聞きなれないかもしれないので，応用事例を一つ挙げてみましょう．
具体例を挙げるだけなので，用語の定義等は省略します．
次の漸化式を考えましょう：
a_{n + 2} = a_{n + 1} + a_n.
Fibonacci 数列ですね．この数列を係数に持つ，形式的整級数を考えます（generating function）：
G (Z) = a_0 + a_1 Z + a_2 Z^2 + \dotsb.
（余談ですが，generating function の訳が母関数というのは言い得て妙だと思います．）
このとき，(G (Z) - a_0) / Z，(G (Z) - a_0 - a_1 Z) / Z^2 という形式的整級数は次の形をしています：
\frac{G (Z) - a_0}{Z} = a_1 + a_2 Z + a_3 Z^2 + \dotsb, \\
\frac{G (Z) - a_0 - a_1 Z}{Z^2} = a_2 + a_3 Z + a_4 Z^2 + \dotsb.
よって，漸化式より次の等式が成り立ちます：
\frac{G (Z) - a_0 - a_1 Z}{Z^2} = \frac{G (Z) - a_0}{Z} + G (Z).
両辺に Z^2 を掛けて整理することで，
G (Z) = \frac{a_0 (Z - 1) - a_1 Z}{Z^2 + Z - 1}
を得ます．
今，多項式 Z^2 + Z - 1 の根を \alpha = (-1 + \sqrt{5}) / 2，\beta = (-1 - \sqrt{5}) / 2 と置けば
\frac{1}{Z^2 + Z - 1} = \frac{1}{\sqrt{5}} \left( \frac{1}{Z - \alpha} - \frac{1}{Z - \beta} \right)
が成り立ち，また形式的整級数として
\frac{1}{Z - a} = - \sum_{n = 0}^\infty a^{- n - 1} Z^n \quad (a \in \mathbb{C}^\times = \mathbb{C} \setminus \{ 0 \})
が成り立つので，結局
\frac{1}{Z^2 + Z - 1} = \frac{1}{\sqrt{5}} \sum \left( \beta^{- n - 1} - \alpha^{- n - 1} \right) Z^n
となり，よく知られた Fibonacci 数列の一般項が出てきました．
母関数の使い方については数学ガールの無印にも解説があるので，そちらも参考にしてください．
このように，漸化式を整級数（母関数と呼ばれる）の言葉で表す手法ですが，一つ欠点があります．
それは，(G - a_0) / Z や (G - a_0 - a_1 Z) / Z^2 のようなよく分からない項が現れてしまうことです．具体的な計算には良いのですが，一般理論を展開する上では微妙なところです．
そこで，ここでは整級数ではなく Laurent 級数として母関数を定義し，その性質を調べていきます．
形式的 Laurent 級数
まず初めに，前回の話は n を整数全体まで広げても成り立つことに注意しておきます．その上で，数列全体のなすベクトル空間 S を
S := \mathrm{Map} (\mathbb{Z}, \mathbb{C}) = \{ (x_n)_{n = - \infty}^\infty \subset \mathbb{C} \}
と定義し直し，数列 (f_n)_n \in S を
f (Z) = \sum_{n = - \infty}^\infty f_n Z^n
と書くことにします．ただし，Z は単なる記号であって，複素数ではありません．数列 (f_n)_n のことを f (Z) = \sum f_n Z^n とそれっぽく書いた，というだけです．
この f (Z) を（形式的）Laurent 級数と呼び，また数列 (f_n)_n の母関数とも呼びます．
Laurent 級数全体のなすベクトル空間を \mathbb{C} [\![ Z, Z^{-1} ]\!] と書きます．つまり，結局のところ \mathbb{C} [\![ Z, Z^{-1} ]\!] = S です．
このベクトル空間 \mathbb{C} [\![ Z^{\pm 1} ]\!] = \mathbb{C} [\![ Z, Z^{-1} ]\!] を Laurent 級数環と呼びます．
その名前に反して，Laurent 級数環 \mathbb{C} [\![ Z^{\pm 1} ]\!] = \mathbb{C} [\![ Z, Z^{-1} ]\!] は（自然な演算の下で）環ではありません．
たとえば
f (Z) = \sum_{n = 0}^\infty Z^n, \ g (Z) = \sum_{n = - \infty}^0 Z^n \in \mathbb{C} [\![ Z^{\pm 1} ]\!]
という Laurent 級数に対して，もし f (Z) g (Z) が定義できるのなら
f (Z) g (Z) = \left( \sum_{n = 0}^\infty Z^n \right) \left( \sum_{m = - \infty}^0 Z^m \right) = \sum_{d = - \infty}^\infty \left( \sum_{n + m = d} 1 \right) Z^d
となることを期待するのですが，無限和 \sum 1 が出てきてしまうので定義できません．
ただ，Laurent 多項式との掛け算は可能です．Laurent 多項式とは有限項の Laurent 級数
\sum_{n = - k}^d f_n Z^n \quad (k, d \in \mathbb{Z}_{\geqslant 0})
のことであり，Laurent 多項式全体のなす環（これは本当に環となります）を \mathbb{C} [Z^{\pm 1}] と書きます．この環を Laurent 多項式環 と呼びます．
Laurent 多項式と Laurent 級数の積は常に定義できます．
言い換えれば，Laurent 級数環 \mathbb{C} [\![ Z^{\pm 1} ]\!] は Laurent 多項式環 \mathbb{C} [Z^{\pm 1}] 上の加群となっています．
漸化式と Laurent 級数
斉次漸化式
漸化式を Laurent 級数の言葉に翻訳するためには，数列 f_\bullet \in S の母関数 G (Z) \in \mathbb{C} [\![ Z^{\pm 1} ]\!] とその k シフト f_\bullet [k] \in S の母関数 G_k (Z) \in \mathbb{C} [\![ Z^{\pm 1} ]\!] の間の関係を確かめる必要があります．
ここで，数列 f_\bullet = (f_n)_n の k シフトとは，(f_\bullet [k])_n = f_{n + k} で定まる数列 f_\bullet [k] のことでした．
Laurent 級数ではなく整級数の場合だと，たとえば
G_1 (Z) = \frac{G (Z) - a_0}{Z}, \\
G_2 (Z) = \frac{G (Z) - a_0 - a_1 Z}{Z^2}
という関係がありました．
Laurent 級数であれば，もっと単純に
G_k (Z) = \frac{1}{Z^k} G (Z)
が成り立つます．ただし右辺は，Laurent 多項式環の元 1/Z^k を，Laurent 級数環の元 G (Z) へ作用させたものです．
すると，
f_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i f_{n + i} \quad (\lambda_0 \in \mathbb{C}^\times, \ \lambda_i \in \mathbb{C})
という斉次漸化式（M \geqslant 2）であれば
\frac{1}{Z^{M - 1}} G (Z) = \sum_{i = 0}^{M - 2} \frac{\lambda_i}{Z^i} G (Z)
となるので，特性多項式（characteristic polynomial）を \chi (t) = t^{M - 1} - \sum \lambda_i t^i \in \mathbb{C} [t] と置いて
を得ます．
結局，漸化式というのは，\chi (Z^{-1}) G (Z) = 0 という（Laurent 級数 G (Z) に関する）方程式を解け，という問題に他ならないことが分かりました．
注意として，\chi (Z^{-1}) G (Z) というのは Laurent 多項式環の Laurent 級数環への作用であって，Laurent 級数環における積とは何も関係ありません．
たとえば次の漸化式
を母関数に翻訳すると，
となります．両辺に Z を掛ければ
となるのですが（ここまでは正しいです），さらに両辺に 1 / (1 - Z) = \sum_{n = 0}^\infty Z^n を掛けて
G (Z) = \left( \sum_{n = 0}^\infty Z^n \right) \cdot (1 - Z) G (Z) = 0
としてはいけません．なぜなら，整級数は Laurent 級数へ作用できないからです．Laurent 多項式環において 1 / (1 - Z) という元は存在しません．1 = (1 - Z) \sum Z^n という等式はあくまで整級数環におけるものであり，Laurent 多項式環では定義されていません．
上のような不当な議論がたまたま上手くいくこともあるかもしれませんが，一般には成り立つこともあれば成り立たないこともあります．
プログラミング風に言えば，\mathbb{C} [\![ Z^{\pm 1} ]\!] に対して仕様上許されているのは \mathbb{C} [Z^{\pm 1}] 加群としての構造だけであり，それ以外の操作は未定義動作というわけです．
非斉次漸化式の特解
前回は，一般論の記述が面倒だったので，特解を求める方法は省略していました．
母関数を使った方法であれば，簡単に特解の表式を求めることができます．（ただ，その表式を具体的に計算するのはやはり面倒ですが……．）
次の非斉次漸化式を考えます：
f_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i f_{n + i} + c \quad (c \in \mathbb{C}).
斉次化した漸化式 f_{n + M - 1} = \sum \lambda_i f_{n + i} の特性多項式を \chi (t) \in \mathbb{C} [t] とすれば，これは \chi (Z^{-1}) G (Z) = c という方程式となります．
（零でない）Laurent 多項式は Laurent 級数環の中で可逆であることに注意しましょう．（言い換えれば，\mathbb{C} [\![ Z^{\pm 1} ]\!] は可除 \mathbb{C} [Z^{\pm 1}] 加群です． ）
実際，整級数環の一般論によって，定数項が零でないような任意の整式 P (Z) \in \mathbb{C} [Z] は整級数環 \mathbb{C} [\![ Z ]\!] の中で可逆です．つまり，P (Z) Q (Z) = 1 となるような整級数 Q (Z) \in \mathbb{C} [\![ Z ]\!] が存在します．
一般の 0 \neq P (Z) \in \mathbb{C} [Z^{\pm 1}] の場合は，P (Z) を適当な P (Z) Z^{\pm n} で置き換えることによって，上の場合に帰着できます．このことから，P (Z) Q (Z) = 1 となるような Laurent 級数 Q (Z) \in \mathbb{C} [\![ Z^{\pm 1} ]\!] の存在が従います．
特に \chi (Z^{- 1}) Q (Z) = 1 となるような Laurent 級数 Q (Z) \in \mathbb{C} [\![ Z^{\pm 1} ]\!] が取れるので，\Pi (Z) := c Q (Z) と置けば \Pi (Z) が漸化式 \chi (Z^{- 1}) \Pi (Z) = c の特解となります（particular solution）．
特解さえ分かれば，漸化式の任意の解 G (Z) \in \mathbb{C} [\![ Z^{\pm 1} ]\!] に対して G (Z) - \Pi (Z) は斉次漸化式 \chi (Z^{-1}) G (Z) = 0 の解となりますし，逆に斉次漸化式の解 G (Z) に対して，\Pi (Z) + G (Z) は非斉次漸化式 \chi (Z^{-1}) G (Z) = c の解となります．
解空間
さて，一般の零でない Laurent 多項式 0 \neq P (Z) \in \mathbb{C} [Z^{\pm 1}] に対して，Laurent 級数 G (Z) に関する方程式 P (Z) G (Z) = 0 の解空間を考えます．
簡単のために，P (t) \in \mathbb{C} [t] を定数項が 0 でないような整式として，P (Z^{-1}) G (Z) = 0 という方程式の解空間を
\mathrm{Ker}\, P = \left\{ G (Z) \in \mathbb{C} [\![Z^{\pm 1}]\!] \,\middle|\, P (Z^{-1}) G (Z) = 0 \right\}
と書きましょう．（これは，スカラー倍写像 P (Z^{-1}) \times の kernel，という気持ちです．）
一般の Laurent 多項式 0 \neq P (Z) \in \mathbb{C} [Z^{\pm 1}] でも，最高次の項を p_d Z^d とするとき，P (Z) を Z^{-d} P (Z) で置き換えることで P (Z) = p_d + p_{d - 1} Z^{-1} + p_{d - 2} Z^{-2} + \dotsb という形にできます．
（Laurent 多項式環の可逆元 Q (Z) に対して，P (Z) G (Z) = 0 と Q (Z) P (Z) G (Z) = 0 が同値であることに注意．）
整式環 \mathbb{C} [Z] や整級数環 \mathbb{C} [\![ Z ]\!] は整域なので，零でないスカラー倍写像の kernel というのは常に 0 でした．
一方，Laurent 級数環では \mathrm{Ker}\, P の次元が \mathrm{ord}\, P となります．ここで，\mathrm{ord}\, P は Laurent 多項式 P (Z^{-1}) の位数（あるいは，整式 P (Z) の次数）を表します．
なぜなら，\mathrm{ord}\, P = k のとき，方程式 P (Z^{-1}) G (Z) = 0 というのは P (Z) を特性多項式とするような k + 1 項間漸化式のことなので，線形写像
\mathbb{C}^k \ni a = (a_i)_i \mapsto G_a (Z) \in \mathrm{Ker}\, P
を得ます．ただし，G_a (Z) は a を初期値とするような漸化式 P (Z^{-1}) G (Z) = 0 の解を表します．このような解が（一意に）存在することは明らかなので，上の写像が線形同型となり，特に \dim \mathrm{Ker}\, P = k が従います．
Z^{-1} \times の固有ベクトル
もっとも簡単な場合は，ある複素数 \psi \in \mathbb{C}^\times を用いて P (Z^{-1}) = Z^{-1} - \psi と書けるときです．
このとき，方程式 (Z^{-1} - \psi) G (Z) = 0 は漸化式 f_{n + 1} = \psi f_n を意味するので，\Psi (Z) := \sum \psi^n Z^n \in \mathbb{C} [\![ Z^{\pm 1} ]\!] は (Z^{-1} - \psi) \Psi (Z) = 0 を満たします．
\mathrm{Ker} (Z^{-1} - \psi) は \mathrm{ord} (Z^{-1} - \psi) = 1 次元なので，\Psi (Z) がこの基底となります．
一般固有ベクトル
スカラー倍写像 Z^{-1} \times の一般固有ベクトルについて調べる前に，偏微分作用素というものを導入しましょう．
偏微分作用素とは，
\partial \left( \sum f_n Z^n \right) := \sum n f_n Z^{n - 1}
で定義される線形作用素 \partial : \mathbb{C} [\![ Z^{\pm 1} ]\!] \to \mathbb{C} [\![ Z^{\pm 1} ]\!] のことです．
この偏微分作用素は次の関係を満たします：
\partial (P f ) = (\partial P ) f + P (\partial f ) \quad \left(P \in \mathbb{C} [Z^{\pm 1}], \ f \in \mathbb{C} [\![ Z^{\pm 1} ]\!] \right).
定義に従って計算するだけで証明できます．
さて，実は
\partial^n \Psi \in \mathrm{Ker} \left( Z^{-1} - \psi \right)^{n + 1} \setminus \mathrm{Ker} \left( Z^{-1} - \psi \right)^n
が成り立ちます．すなわち，(Z^{-1} - \psi)^n \partial^n \Psi (Z) \neq 0 かつ (Z^{-1} - \psi)^{n + 1} \partial^n \Psi (Z) = 0 が成り立ちます．
上の関係を n に関する帰納法で示します．
簡単のために P (Z) = Z^{-1} - \psi と置きましょう．（Z と Z^{-1} が逆．）
まず n = 0 のときはすでに分かっています．
n - 1 のときの等式
P (Z)^n \partial^{n - 1} \Psi (Z) = 0
の両辺を偏微分すると，
0 = \partial P^n \cdot \partial^{n - 1} \Psi + P^n \partial^n \Psi = - \frac{n P^{n - 1}}{Z^2} \partial^{n - 1} \Psi + P^n \partial^n \Psi
となります．
ここから，
P^n \partial^n \Psi = \frac{n P^{n - 1}}{Z^2} \partial^{n - 1} \Psi
を得ますが，P^{n - 1} \partial^{n - 1} \Psi \neq 0 という仮定より，P^n \partial^n \Psi \neq 0 が従います．
一方，両辺に P を掛ければ
P^{n + 1} \partial^n \Psi = - \frac{n P^n}{Z^2} \partial^{n - 1} \Psi = 0
となるので，n のときの主張がすべて示されました．
線形代数の一般論より，ある線形作用素 T \neq 0 とその固有値 \psi に対して v_n \in \mathrm{Ker}\, T^{n + 1} \setminus \mathrm{Ker}\, T^n なるベクトルを（T^n \neq 0 であるような n に対して）任意に取ったとき，\{ v_0, \dotsc, v_n, \dotsc \} は線形独立なので，\{ \partial^i \Psi (Z) \mid i \geqslant 0 \} は線形独立です．
（任意の n に対して \partial^n \Psi \in \mathrm{Ker} ( Z^{-1} - \psi )^{n + 1} \setminus \mathrm{Ker} ( Z^{-1} - \psi )^n なので，特に (Z^{-1} - \psi)^n \neq 0 が分かります．）
\mathrm{Ker} (Z^{-1} - \psi)^m は m 次元なので，\{ \partial^i \Psi (Z) \mid 0 \leqslant i \leqslant m - 1 \} が基底となります．
蛇足ですが，前回の q という作用素との関係も見ておきます．
q は数列 f_\bullet = (f_n)_n \in S に対して (q f_\bullet)_n := n f_n で定まる線形作用素で，\{ q^i \Psi (Z) \mid 0 \leqslant i \leqslant m - 1 \} が \mathrm{Ker} (Z^{-1} - \psi)^m の基底である，というのが前回の内容でした．
この q は今回の記号を使えば q = Z \partial と書けます．
今，線形作用素として Z \partial = \partial Z - 1 が成り立つ（つまり，任意の Laurent 級数 f (Z) に対して Z \partial f = \partial (Z f) - f が成り立つ）ので，
q \Psi = \partial (Z \Psi) - \Psi = \psi^{-1} \partial \Psi - \Psi
となり，q \Psi が \partial^0 \Psi と \partial^1 \Psi の線形結合で書けました．
同様の計算によって q^2 = Z \partial Z \partial = \partial^2 Z^2 - 3 \partial Z + 1 となるので，q^2 \Psi = \psi^{-2} \partial^2 \Psi - 3 \psi^{-1} \partial \Psi + \Psi です．
証明は省略しますが，各 n について，q^n が \{ \partial^i Z^i \mid 0 \leqslant i \leqslant n \} の線形結合で書ける，ということが帰納的に分かるので，q^n \Psi は \{ \partial^i \Psi \mid 0 \leqslant i \leqslant n \} の線形結合で書けます．
ただし，q^n は \{ \partial^i \} の線形結合では書けません．あくまで \Psi へ作用した場合のみです．
斉次漸化式の一般解
ここまで来たら一般の斉次漸化式 \chi (Z^{-1}) G (Z) = 0 の解もすぐに求まります．
まず特性多項式の相異なる根を \psi_1, \dotsc, \psi_\ell \in \mathbb{C}^\times として，それぞれの重複度を \mu_1, \dotsc, \mu_\ell としましょう．
（\chi (0) = \lambda_0 \neq 0 なので \chi は 0 を根に持ちません．）
この解空間 \mathrm{Ker}\, \chi (Z^{-1}) の次元は \mathrm{ord}\, \chi (Z^{-1}) = \deg \chi (t) = M - 1 でしたから，M - 1 個の線形独立な解が分かれば終わりです．
しかし，各 1 \leqslant m \leqslant \ell に対して \{ \partial^i \Psi_m \mid 0 \leqslant i \leqslant \mu_m - 1 \} は (Z^{-1} - \psi_m)^{\mu_m} G (Z) = 0 の解でした．
よって
\chi (Z^{-1}) \partial^i \Psi_m = \left( \prod_{p \neq m} (Z^{-1} - \psi_p)^{\mu_p} \right) (Z^{-1} - \psi_m)^{\mu_m} \partial^i \Psi_m = 0,
従って \{ \partial^i \Psi_m \mid 1 \leqslant m \leqslant \ell, \ 0 \leqslant i \leqslant \mu_m \} が解空間 \mathrm{Ker}\, \chi(Z^{-1}) の基底となります．
終わりに
以上，前回の理論の母関数による焼き直しでした．
同じ数列でも，差分演算子を考えるか冪級数として捉えるかによって大きく見え方が変わるのは面白いですね．
また，冪級数も整級数なのか Laurent 級数なのかによってまったくの別物になります．とても不思議です．
Laurent 級数環はそれ自身非常に興味深い対象なので，よかったら自分の手で遊んでみてください．
Discussion