文献あり

超幾何数列の基礎1：閉形式

961

はじめに

　このシリーズでは超幾何数列という対象の基本事項についてまとめていきます。
　内容としては"A=B"という書籍の第II章から要点を抜き出してまとめていくので、より詳しい話が知りたい人は同書などを参照してください。ちなみに"A=B"は公式のpdf が公開されているので誰でも閲覧することができます。

定義

hypergeometric term

　 $0$ でない数列 $A (n)$ が超幾何数列であるとは、その階比
$\frac{A (n + 1)}{A (n)}$
が $n$ についての有理関数となることを言う。

　隣り合う項の比が一定であるような数列、つまり等比数列のことを時に幾何数列(geometric sequence)と言うことがあり、超幾何数列(hypergeometric sequence)はその一般化として考えられた概念となります。
　超幾何数列はその階比を
$\frac{A (n + 1)}{A (n)} = \frac{(a_{1} + n) \dots (a_{p} + n)}{(b_{1} + n) \dots (b_{q} + n)} z$
と因数分解すると、その一般項はポッホハマー記号
$(x)_{n} = {\begin{cases} x (x + 1) \dots (x + n - 1) & (n \geq 0) \\ \frac{1}{(x - 1) \dots (x + n)} & (n < 0) \end{cases}$
を用いて
$A (n) = A (0) \frac{(a_{1})_{n} \dots (a_{p})_{n}}{(b_{1})_{n} \dots (b_{q})_{n}} z^{n}$
と表せます( $a_{j}$ や $b_{j}$ の値によっては $0$ 除算が発生することもありますが、あまり気にしないこととします)。

呼称について

　hypergeometric "sequence"はしばしばhypergeometric "term"と呼ばれますが、それはこのように超幾何級数
$_{p} F_{q} (\begin{matrix} a_{1}, \dots, a_{p} \\ b_{1}, \dots, b_{q} \end{matrix}; z) = \sum_{n = 0}^{\infty} \frac{(a_{1})_{n} \dots (a_{p})_{n}}{(b_{1})_{n} \dots (b_{q})_{n}} \frac{z^{n}}{n!}$
の $n$ 項目( $n$ -th term)として現れる数列であることを由来としています。
　また呼称としてはhypergeometric "term"の方が一般的であり、直訳するなら超幾何"項"と言うのが適当ですが、個人的な好みによりこのシリーズでは超幾何"数列"という呼称を採用することにしています。

閉形式

　我々が超幾何数列を考える上で関心が高いのはその総和、例えば
$S (n) = \sum_{k = 0}^{n - 1} A (k)$
などが"閉じた形"に表せるか、ということにあります。
　次回以降の記事でこのような問題を考えていくために、今回の記事ではまず"閉じた形"とは具体的にどのような表示のことを指すのか、そして与えられた数列が"閉じた形"に表せるかどうかはどのように判別できるのか、ということについて解説していきます。

定義

　超幾何数列全体のなす集合を $H$ 、 $H$ によって生成される線形空間を $L (H)$ とおく。

ちょっと細かい話

　 $0$ でない数列 $A (n)$ が体 $K$ 上の超幾何数列であるとは、その階比が
$\frac{A (n + 1)}{A (n)} \in K (n)$
を満たすことを言う。
　また $K$ 上の超幾何数列全体のなす集合を $H_{K}$ 、 $H$ によって生成される $K$ -線形空間を $L (H_{K})$ とおく。このとき $L (H_{K})$ は $K (n)$ -線形空間ともみなせることに注意する。

closed form

　数列 $f (n)$ が閉形式であるとは $f (n) \in L (H)$ であること、つまりある超幾何数列 $A_{1} (n), \dots, A_{r} (n)$ が存在して
$f (n) = \sum_{k = 1}^{r} A_{k} (n)$
と表せることを言う。

　例えば幾何数列の部分和
$\sum_{k = 0}^{n - 1} z^{n} = \frac{z^{n} - 1}{z - 1}$
は二つの超幾何数列
$\frac{z^{n}}{z - 1}, - \frac{1}{z - 1}$
の和として表せているので、これは閉形式となります。

相似関係

　まず超幾何数列の和を考える上で重要となる相似という関係について紹介しておきましょう。

similar

　超幾何数列 $A (n), B (n)$ が相似であるとはその比 $A (n) / B (n)$ が $n$ についての有理関数として表せることを言い、そのことを $A (n) \sim B (n)$ と表す。これによって定まる $H$ の二項関係 $\sim$ は同値関係をなす。

　超幾何数列 $A (n), B (n)$ に対し、 $A (n) + B (n)$ が超幾何数列または $0$ であることと $A (n) \sim B (n)$ であることは同値である。

証明

　 $A (n) + B (n) = 0$ のときは明らか。いま $A (n) + B (n) \neq 0$ とし
$R_{A} (n) = \frac{A (n + 1)}{A (n)}, R_{B} (n) = \frac{B (n + 1)}{B (n)}, R_{A / B} (n) = \frac{A (n)}{B (n)}, R_{A + B} (n) = \frac{A (n + 1) + B (n + 1)}{A (n) + B (n)}$
とおく。このとき $R_{A / B} (n)$ が有理関数であることと $R_{A + B} (n)$ が有理関数であることは同値となることを示せばよい。
　そのことは
$R_{A + B} (n) = \frac{R_{A} (n) R_{A / B} (n) + R_{B} (n)}{R_{A / B} (n) + 1}$
およびこれを $R_{A / B} (n)$ について整理することで
$R_{A / B} (n) = - \frac{R_{A + B} (n) - R_{B} (n)}{R_{A + B} (n) - R_{A} (n)}$
が成り立つことに注意するとわかる。

　超幾何数列 $A_{1} (n), \dots, A_{r} (n)$ が
$\sum_{k = 1}^{r} A_{k} (n) = 0$
を満たすとき、ある $i \neq j$ に対し $A_{i} (n) \sim A_{j} (n)$ が成り立つ。

証明

　 $r$ についての数学的帰納法によって示す。 $r = 2$ のときは明らか。
　いま
$R_{k} (n) = \frac{A_{k} (n + 1)}{A_{k} (n)}$
とおくと命題の仮定より
$\sum_{k = 1}^{r} A_{k} (n + 1) = \sum_{k = 1}^{r} R_{k} (n) A_{k} (n) = 0$
および
$R_{r} (n) \sum_{k = 1}^{r} A_{k} (n) = 0$
が成り立つのでこの差を取ることで
$\sum_{k = 1}^{r - 1} (R_{r} (n) - R_{k} (n)) A_{k} (n) = 0$
が得られる。
　このときある $k$ に対して $R_{r} (n) - R_{k} (n) = 0$ であれば
$\frac{A_{r} (n + 1)}{A_{k} (n + 1)} = \frac{A_{r} (n)}{A_{k} (n)}$
つまり $A_{r} (n) / A_{k} (n)$ は定数となるので $A_{r} (n) \sim A_{k} (n)$ が成り立つ。
　また全ての $k$ に対して $R_{r} (n) - R_{k} (n) \neq 0$ であれば、帰納法の仮定よりある $i \neq j$ に対して
$(R_{r} (n) - R_{i} (n)) A_{i} (n) \sim (R_{r} (n) - R_{j} (n)) A_{j} (n)$
が成り立ち、 $R_{r} (n) - R_{k} (n)$ は有理関数であることから $A_{i} (n) \sim A_{j} (n)$ がわかる。

　 $0$ でない任意の $f (n) \in L (H)$ に対し、ある互いに相似でない超幾何数列 $A_{1} (n), \dots, A_{r} (n)$ が存在して
$f (n) = \sum_{k = 1}^{r} A_{k} (n)$
が成り立つ。またこのような表示は一意的である。

証明

　 $L (H)$ の定義から $f (n)$ はある超幾何数列 $B_{1} (n), \dots, B_{r} (n)$ を用いて
$f (n) = \sum_{k = 1}^{r} B_{k} (n)$
と表せる。このときある $i \neq j$ に対し $B_{i} (n) \sim B_{j} (n)$ であればこれは再び超幾何数列(または $0$ )となるので一項にまとめることができ、このように項をまとめていくことで主張のような表示が得られる。
　いま二通りの表示
$f (n) = \sum_{k = 1}^{r} A_{k} (n) = \sum_{k = 1}^{r^{'}} A_{k}^{'} (n)$
が得られたとき、適当に順番を入れ替え相似なもの同士をまとめることで
$\sum_{k = t}^{s} (A_{k} (n) - A_{k}^{'} (n)) + \sum_{k = s}^{r} A_{k} (n) - \sum_{j = s}^{r^{'}} A_{k}^{'} (n) = 0$
は互いに相似でない超幾何数列の和となる。したがって命題2よりこの左辺は空和、つまり
$A_{k} (n) = A_{k} (n) (k = 1, 2, \dots)$
でなければならないことがわかる。

　この命題から互いに相似でない超幾何数列は $K (n)$ -線形独立となることに注意しましょう(ただし $K (n)$ は有理関数体としました)。

閉形式と漸化式

　では与えられた数列 $f (n)$ が $L (H)$ に属すかどうかを判別する方法について解説していきましょう。
　結論から言うとこの問題は $f (n)$ の満たす漸化式を調べることで解決されます。

P-recursive

　数列 $f (n)$ がP-再帰的であるとは $f (n)$ が多項式係数の線形漸化式を満たす、つまりある多項式 $p_{0} (n), \dots, p_{I} (n) (p_{I} (n) \neq 0)$ が存在して
$\sum_{i = 0}^{I} p_{i} (n) f (n + i) = 0$
が成り立つことを言う。

　ちなみに定数係数の線形漸化式を満たすことはC-再帰的であると言い、このPやCは多項式(Polynomial)や定数(Constant)の頭文字を取っています。

　任意の $f (n) \in L (H)$ はP-再帰的である。

　明らかに各 $A (n) \in H$ はP-再帰的であるので次の主張を示せばよい。

　P-再帰的な数列 $f (n), g (n)$ に対し $f (n) + g (n)$ もP-再帰的となる。

　この事実については昔にこんな記事を書いたことがあります。一応その記事と同じ証明を下においておきます。

証明

　 $f, g$ がそれぞれ漸化式
$\sum_{k = 0}^{r} p_{k} (n) f (n + k) = \sum_{k = 0}^{s} q_{k} (n) g (n + k) = 0$
を満たすとする。このとき
$h (n) = f (n) + g (n), t = r + s$
とし
$h (n + k) (0 \leq k \leq t)$
を縦に並べたベクトルを $γ$
$f (n + i), g (n + j) (0 \leq i < r, 0 \leq j < s)$
を適当に整列させて縦に並べたベクトルを $Γ$ とおく。
　このとき $f, g$ の漸化式を用いることである有理関数を係数に持つ $(t + 1) \times t$ 行列 $P (n)$ が存在して
$γ = P (n) Γ$
と表せ、 $P (n)$ サイズからある多項式係数の $t + 1$ 次元横ベクトル $r (n)$ が存在して
$r (n) P (n) = 0$
が成り立つので $h (n)$ は漸化式
$r (n) γ = \sum_{k = 0}^{t} r_{k} (n) h (n + k) = 0$
を満たすことがわかる。

　 $f (n) \in L (H)$ が漸化式
$\sum_{i = 0}^{I} p_{i} (n) f (n + i) = 0$
を満たすとき、命題3のような分解
$f (n) = \sum_{k = 1}^{r} A_{k} (n)$
における各因子 $A_{k} (n)$ も漸化式
$\sum_{i = 0}^{I} p_{i} (n) A_{k} (n + i) = 0$
を満たす。

証明

$\frac{A_{k} (n + i)}{A_{k} (n)}$
は有理関数となることに注意するとある有理関数 $R_{k} (n)$ が存在して
$\sum_{i = 0}^{I} p_{i} (n) A_{k} (n + i) = R_{k} (n) A_{k} (n)$
と表せる。このとき
$\sum_{i = 0}^{I} p_{i} (n) f (n + i) = \sum_{k = 1}^{r} R_{k} (n) A_{k} (n) = 0$
が成り立つので、命題3より $A_{1} (n), \dots, A_{r} (n)$ は $C (n)$ -線形独立であったことに注意すると各 $k$ に対し $R_{k} (n) = 0$ つまり
$\sum_{i = 0}^{I} p_{i} (n) A_{k} (n + i) = 0$
となることがわかる。

　 $r \leq I$ が成り立つ。

証明

　一般に $I$ 項間線形漸化式
$\sum_{i = 0}^{I} p_{i} (n) f (n + i) = 0 (p_{I} (n) \neq 0)$
の解空間は高々 $I$ 次元となるので $A_{1} (n), \dots, A_{r} (n)$ が線形独立であることから $r \leq I$ となることがわかる。

まとめ

　上で紹介した事実をまとめると数列 $f (n)$ が閉形式に表せるか否かは次のようなステップによって判別することができます。

$f (n)$ が満たす多項式係数の線形漸化式を求める。
$f (n)$ と同じ漸化式を満たす超幾何数列を全て求める。
$f (n)$ がそれらの線型結合として表せるかを調べる。

　ステップ1については一般的な方法があるわけではありませんが、第二回の記事や第四回の記事で扱うような特定の対象を考える場合は $f (n)$ が満たす漸化式を求めるアルゴリズムが確立されています。
　ステップ2については一般的な方法、つまり与えられた漸化式に対してそれを満たす超幾何数列を網羅的に求めるアルゴリズムが確立されています。詳しい方法については第三回の記事にて解説していきます。
　ステップ3については線形漸化式の一般論から連続する $I$ 個の値、例えば $n = 0, 1, \dots, I - 1$ に対して
$f (n) = \sum_{k = 1}^{r} c_{k} A_{k} (n)$
が成り立つような線型結合 $c_{0}, \dots, c_{r}$ の取り方が存在すれば一般の $n$ に対してもこれが成り立つことがわかり、逆にそのような線型結合の取り方が存在しなければ $f (n)$ は閉形式に表せないことになります。