文献あり

超幾何数列の基礎2：望遠鏡和の作り方

753

はじめに

　この記事では前回の記事に引き続き超幾何数列の基本事項についてまとめていきます。
　今回の記事では超幾何数列の部分和
$S (n) = \sum_{k = 0}^{n - 1} A (k)$
の閉形式の求め方について解説していきます。

Gosper総和可能性

　超幾何数列の部分和 $S (n)$ は
$S (0) = 0, S (n + 1) - S (n) = A (n)$
という漸化式によって特徴づけられる数列であり、また
$\frac{A (n + 1)}{A (n)} = \frac{p (n)}{q (n)}$
なる多項式 $p (n), q (n)$ を取ると三項間漸化式
$q (n) (S (n + 2) - S (n + 1)) - p (n) (S (n + 1) - S (n)) = 0$
が成り立つ、つまり $S (n)$ はP-再帰的であることがわかります。
　したがって $S (n)$ の閉形式を考えることができ、また閉形式が存在すればそれは以下のような形になることがわかります。

　超幾何数列 $A (n)$ の部分和
$S (n) = \sum_{k = 0}^{n - 1} A (k)$
が閉形式を持つとき、それは漸化式
$T (n + 1) - T (n) = A (n)$
を満たす超幾何数列 $T (n)$ を用いて
$S (n) = T (n) - T (0)$
と表せる。

証明

　互いに相似でない超幾何数列 $T_{1} (n), \dots, T_{r} (n)$ を用いて
$S (n) = \sum_{k = 1}^{r} T_{k} (n)$
と表したとき、この差分を取ることで
$A (n) = \sum_{k = 1}^{r} (T_{k} (n + 1) - T_{k} (n))$
が成り立つ。このとき $T_{k} (n + 1) - T_{k} (n)$ は $0$ でなければ $T_{k} (n)$ と相似であること、および前回の記事の命題3(の一意性の部分)に注意すると上の式は
$A (n) = T_{1} (n + 1) - T_{1} (n)$
のようでなければならない。
　したがって $T (n) = T_{1} (n)$ とおくと
$\begin{aligned} S (n) & = \sum_{k = 0}^{n - 1} A (k) \\ = \sum_{k = 0}^{n - 1} (T (k + 1) - T (k)) \\ = T (n) - T (0) \end{aligned}$
を得る。

Gosper-summable

　超幾何数列 $A (n)$ がGosper総和可能であるとは、漸化式
$T (n + 1) - T (n) = A (n)$
を満たすような超幾何数列 $T (n)$ が存在することを言う。

　ちなみに
$S (n) = \sum_{k = 0}^{n - 1} (T (k + 1) - T (k)) = T (n) - T (0)$
のような変形(ができる和)のことを望遠鏡和(telescoping sum)と言い、また
$A (n) = T (n + 1) - T (n)$
のような $T (n)$ を見つけることで $A (n)$ についての和を望遠鏡和の形に変形する手法のことをcreative telescopingといいます。

問題の帰着

　ではどのようなときに $A (n)$ がGosper総和可能であり、そのときどのようにして $T (n)$ を求められるのかを考えていきましょう。

数列から有理関数へ

　超幾何数列 $A (n), T (n)$ が
$T (n + 1) - T (n) = A (n)$
を満たすとき
$r (n) = \frac{A (n + 1)}{A (n)}, y (n) = \frac{T (n)}{A (n)}$
とおくと $r (n), y (n)$ は有理関数であり
$r (n) y (n + 1) - y (n) = 1$
が成り立つ。

証明

　 $y (n)$ が有理関数であることは
$y (n) = \frac{T (n)}{T (n + 1) - T (n)} = \frac{1}{\frac{T (n + 1)}{T (n)} - 1}$
とわかる。また
$\frac{T (n + 1)}{A (n)} = \frac{A (n + 1)}{A (n)} \frac{T (n + 1)}{A (n + 1)} = r (n) y (n + 1)$
に注意すると
$\frac{T (n + 1) - T (n)}{A (n)} = r (n) y (n + 1) - y (n) = 1$
を得る。

　この補題により与えられた超幾何数列 $A (n)$ に対し
$T (n + 1) - T (n) = A (n)$
を満たすような超幾何数列 $T (n)$ を求める問題は、与えられた有理関数 $r (n)$ に対して
$r (n) y (n + 1) - y (n) = 1$
を満たすような有理関数 $y (n)$ を求める問題に帰着されます。

有理関数から多項式へ

　 $0$ でない有理関数 $r (n)$ に対して
$r (n) = \frac{a (n)}{b (n)} \frac{c (n + 1)}{c (n)}$
なる多項式 $a (n), b (n), c (n)$ であって以下を満たすようなものが存在する。

任意の非負整数 $h$ に対し $a (n)$ と $b (n + h)$ は互いに素である。

証明

　互いに素な多項式 $f (n), g (n)$ を用いて
$r (n) = \frac{f (n)}{g (n)}$
と表したとき、ある正整数 $h$ に対し $f (n)$ と $g (n + h)$ が共通因子 $u (n)$ を持つとすると
$\begin{aligned} f (n) & = \overset{―}{f} (n) u (n) \\ g (n) & = \overset{―}{g} (n) u (n - h) \\ U (n) & = u (n - 1) u (n - 2) \dots u (n - h) \end{aligned}$
とおけば
$r (n) = \frac{\overset{―}{f} (n)}{\overset{―}{g} (n)} \frac{u (n)}{u (n - h)} = \frac{\overset{―}{f} (n)}{\overset{―}{g} (n)} \frac{U (n + 1)}{U (n)}$
が成り立つ。
　このように各 $h = 1, 2, \dots$ に対し $f (n), g (n + h)$ の共通因子を掃き出していくことで所望の多項式 $a (n), b (n), c (n)$ を構成できることがわかる。

　いま補題2のような多項式 $a (n), b (n), c (n)$ を取り
$y (n) = \frac{b (n - 1)}{c (n)} x (n)$
とおくと考えている方程式は
$a (n) x (n + 1) - b (n - 1) x (n) = c (n)$
と変形できます。そして、驚くべきことに、以下のような事実が成り立ちます。

　補題3の(i)を満たすような多項式 $a (n), b (n), c (n)$ に対し
$a (n) x (n + 1) - b (n - 1) x (n) = c (n)$
なる有理関数 $x (n)$ が存在すれば $x (n)$ は多項式となる。

証明

　 $x (n)$ を互いに素な多項式 $f (n), g (n)$ を用いて
$x (n) = \frac{f (n)}{g (n)}$
と表したとき $g (n)$ が定数でないものと仮定し矛盾を導く。
　いま $g (n)$ の既約因子 $u (n)$ を任意に取り、適当に平行移動させることで $u (n)$ は
$u (n) ∣ g (n) かつ u (n + 1) ∤ g (n)$
を満たすものとしてよい。また $N \geq 0$ を
$u (n - N) ∣ g (n) かつ u (n - N) ∤ g (n + 1)$
を満たすような整数、例えば $u (n - N) ∣ g (n)$ を満たすような整数であって最大のものとする。
　このとき $x (n)$ の満たす等式
$a (n) \frac{f (n + 1)}{g (n + 1)} - b (n - 1) \frac{f (n)}{g (n)} = c (n)$
の分母に注目すると
$u (n + 1) ∣ a (n) かつ u (n - N) ∣ b (n - 1)$
が成り立たなければならないが
$u (n + 1) ∣ a (n), b (n + N)$
となって $a (n), b (n)$ の取り方に矛盾。
　よって $g (n)$ は定数でなければならないことが示された。

まとめ

　以上の議論をまとめると超幾何数列 $A (n)$ のGosper総和可能性や
$T (n + 1) - T (n) = A (n)$
なる超幾何数列 $T (n)$ は次のようなステップによって求めることができます。

多項式 $a (n), b (n), c (n)$ であって
$\frac{A (n + 1)}{A (n)} = \frac{a (n)}{b (n)} \frac{c (n + 1)}{c (n)}$
かつ、任意の非負整数 $h$ に対して
$gcd (a (n), b (n + h)) = 1$
となるようなものを求める。
方程式
$a (n) x (n + 1) - b (n - 1) x (n) = c (n)$
を満たすような多項式 $x (n)$ を求める。
$x (n)$ が求まらなければ $A (n)$ はGosper総和不可能であり、 $x (n)$ が求まれば
$T (n) = \frac{b (n - 1)}{c (n)} x (n) A (n)$
が求める超幾何数列となる。

Gosper's Algorithm

　基本的には上の手順に沿って計算をすることで $T (n)$ を求めることができますが、 $A (n)$ の与えられ方によってはこれを手計算で実行するのが現実的でないことも少なくありません。そういうときでも $T (n)$ を求められるように、より機械的に処理する方法も考えておきましょう。

ステップ1について

　まずは与えられた有理関数 $r (n)$ に対してステップ1のような多項式 $a (n), b (n), c (n)$ を求める方法について考えていきましょう。と言っても大筋は補題3の証明の通り、つまり $r (n) = f (n) / g (n)$ と表したとき各 $h = 1, 2, \dots$ に対し $f (n), g (n + h)$ の共通因子を掃き出していくことで求められます。
　ただし計算上は $h = 1, 2, \dots$ と無限に続けていくわけにはいかないので、事前に $f (n)$ と $g (n + h)$ が共通因子を持ち得るような $h$ の範囲を求めておく必要があります。それには終結式という概念が重要な役割を果たします。
　終結式の定義などについては特に解説しませんが、多項式 $p, q$ についての終結式 $Res (p, q)$ は $p, q$ の係数から求まる値であり、 $p, q$ が共通因子を持つことと $Res (p, q) = 0$ となることは同値であることが知られています。特に $f (n), g (n + h)$ についての終結式 $R (h)$ は $h$ についての多項式として表せ、これによって $R (h) = 0$ となるような正整数 $h$ の値を列挙することができます。
　以上のことをまとめるとこの問題は次のようなアルゴリズムによって解決することができます。

互いに素な多項式 $f (n), g (n)$ であって
$r (n) = \frac{f (n)}{g (n)}$
を満たすようなものを求める。
非負整数 $h$ であって
$R (h) = Res (f (n), g (n + h))$
を $0$ とするようなものを全て求め、それらを小さい順に
$h = h_{1}, h_{2}, \dots, h_{N}$
とおく。
多項式列 $f_{j} (n), g_{j} (n), u_{j} (n)$ を
$f_{0} (n) = f (n), g_{0} (n) = g (n)$
および漸化式
$\begin{aligned} u_{j} (n) & = gcd (f_{j - 1} (n), g_{j - 1} (n + h_{j})) \\ f_{j} (n) & = f_{j - 1} (n) / u_{j} (n) \\ g_{j} (n) & = g_{j - 1} (n) / u_{j} (n - h_{j}) \end{aligned}$
によって定める。このとき
$\begin{array}{l} a (n) = f_{N} (n) \\ b (n) = g_{N} (n) \\ c (n) = \prod_{j = 1}^{N} u_{j} (n - 1) \dots u_{j} (n - h_{j}) \end{array}$
が求める多項式となる。

　ちなみにこのようにして求められた $a (n), b (n), c (n)$ は次のような性質を満たします。

任意の非負整数 $h$ に対し $a (n)$ と $b (n + h)$ は互いに素である。
$a (n)$ と $c (n)$ は互いに素である。
$b (n)$ と $c (n + 1)$ は互いに素である

また上のアルゴリズムによって得られる多項式はこれを満たす。

証明

　上のアルゴリズムによって得られる多項式を $a (n), b (n), c (n)$ とおいたとき、これらが(i),(ii),(iii)を満たすことを示せばよい((i)については明らか)。

(ii)について

　もし $a (n)$ と $c (n)$ が互いに素でなければ、 $c (n)$ の定め方からある $i, j$ に対して $u_{j} (n - i)$ は $a (n)$ と共通因子 $v (n)$ を持つことになる。このとき $a (n)$ は $f_{j - 1} (n)$ を割り切るので $f_{j - 1} (n)$ も $v (n)$ を因数に持ち、また
$g_{j - 1} (n + h_{j} - i) = g_{j} (n + h_{j} - i) u_{j} (n - i)$
より $g_{j - 1} (n + h_{j} - i)$ も $v (n)$ を因数に持つが、 $f_{j - 1}, g_{j - 1}, h_{j}$ の定め方から任意の $0 \leq h < h_{j}$ に対して $f_{j - 1} (n)$ と $g_{j - 1} (n + h)$ は互いに素であったことに矛盾。よって $a (n)$ と $c (n)$ は互いに素でなければならない。

(iii)について

　(ii)の場合と同様に $b (n)$ と $c (n + 1)$ が互いに素でなければある $i, j$ に対して $u_{j} (n - i + 1)$ は $b (n)$ と共通因子 $v (n)$ を持つことになり、このとき $v (n + i - 1)$ は $f_{j - 1} (n), g_{j - 1} (n + i - 1)$ を共に割り切ることがわかるので矛盾を得る。

ステップ2について

　次に与えられた多項式 $a (n), b (n), c (n)$ に対して
$a (n) x (n + 1) - b (n - 1) x (n) = c (n)$
を満たすような多項式 $x (n)$ を求める方法について考えていきましょう。
　と言っても多項式の恒等式なので適当に $d$ を取って
$x (n) = \sum_{k = 0}^{d} C_{k} n^{k}$
と展開し係数比較することによって $d + 1$ 個の未知数 $C_{0}, \dots, C_{d}$ についての線型方程式に帰着させるだけではあります。
　ただ求める解が存在しない場合も考慮して $d = \deg x (n)$ の取り得る値を求めておく必要があります。いま $a (n)$ と $b (n)$ の最高次の係数が打ち消し合う場合と打ち消し合わない場合の二通りに分けて考えてみましょう。　

打ち消し合わない場合

　このときは件の方程式
$a (n) x (n + 1) - b (n - 1) x (n) = c (n)$
における左辺の次数は $d + max {\deg a (n), \deg b (n)}$ となるので
$d = \deg c (n) - max {\deg a (n), \deg b (n)}$
と求まります。

打ち消し合う場合

　このとき $a (n), b (n - 1), x (n)$ を
$\begin{aligned} a (n) & = λ n^{k} + A n^{k - 1} + \dots \\ b (n - 1) & = λ n^{k} + B n^{k - 1} + \dots \\ x (n) & = C n^{d} + C^{'} n^{d - 1} + \dots \end{aligned}$
と展開すると
$\begin{aligned} c (n) & = a (n) x (n + 1) - b (n - 1) x (n) \\ = a (n) (x (n + 1) - x (n)) + (a (n) - b (n - 1)) x (n) \end{aligned}$
の右辺における $n^{k + d - 1}$ の係数は $C (λ d + A - B)$ と表せます。
　したがってこれが $0$ でなければ
$d = \deg c (n) - k + 1$
と求まり、これが $0$ であれば
$d = \frac{B - A}{λ}$
と求まります。

まとめ

　以上のことをまとめるとこの問題は次のようなアルゴリズムによって解決することができます。

　 $k = max {\deg a, \deg b}$ とし $a (n), b (n - 1)$ の $k, k - 1$ 次の係数をそれぞれ $λ_{a}, λ_{b}, A, B$ とおく。

$\deg a (n) \neq \deg b (n)$ または $λ_{a} \neq λ_{b}$ が成り立つとき
$d = \deg c - k$
$\deg a (n) = \deg b (n)$ かつ $λ_{a} = λ_{b} = λ$ が成り立つとき
$d = {\begin{array}{cl} \deg c - k + 1 & (\frac{B - A}{λ} \notin Z のとき) \\ max {\deg c - k + 1, \frac{B - A}{λ}} & (\frac{B - A}{λ} \in Z のとき) \end{array}$
とおく。
このとき $d < 0$ であれば求めるような多項式 $x (n)$ は存在せず、そうでなければ
$x (n) = \sum_{k = 0}^{d} C_{k} n^{k}$
と展開し
$a (n) x (n + 1) - b (n - 1) x (n) = c (n)$
の両辺を係数比較することによって得られる $C_{0}, \dots, C_{d}$ についての方程式を解く。
もしその方程式が解を持たなければ求めるような多項式 $x (n)$ は存在しない。

計算例

　以上がGosper's algorithmの全容となります。
　と言ってもアルゴリズムの説明だけではいまいちパッとしないと思うので、ここからは"A=B"に載っているいくつかの簡単な例に対してGosper's algorithmがどのように機能するのかを見ていくこととしましょう。

$\sum_{k = 0}^{n} (4 k + 1) \frac{k!}{(2 k + 1)!}$
を閉形式に表せ。

解説

ステップ1

$A (n) = (4 n + 1) \frac{n!}{(2 n + 1)!}$
とおくと
$\begin{aligned} \frac{A (n + 1)}{A (n)} & = \frac{(4 n + 5) (n + 1)}{(4 n + 3) (2 n + 2) (2 n + 3)} \\ = \frac{1}{2 (2 n + 3)} \frac{4 n + 5}{4 n + 1} \end{aligned}$
と表せるので
$a (n) = 1, b (n) = 2 (2 n + 3), c (n) = 4 n + 1$
とおくとよい。

ステップ2

　このとき $x (n)$ の次数は
$d = \deg c (n) - \deg b (n) = 0$
と求まるので $x (n) = K$ とおくと
$\begin{aligned} a (n) x (n + 1) - b (n - 1) x (n) & = K (1 - 2 (2 n + 1)) \\ = - K (4 n + 1) \\ = - K c (n) \end{aligned}$
より $K = - 1$ を得る。

ステップ3

　以上より
$\begin{aligned} T (n) & = \frac{b (n - 1)}{c (n)} x (n) A (n) \\ = - \frac{2 (2 n + 1)}{4 n + 1} \cdot (4 n + 1) \frac{n!}{(2 n + 1)!} \\ = - 2 \frac{n!}{(2 n)!} \\ \sum_{k = 0}^{n} A (k) & = T (n + 1) - T (0) \\ = 2 - 2 \frac{(n + 1)!}{(2 n + 2)!} \\ = 2 - \frac{n!}{(2 n + 1)!} \end{aligned}$
を得る。

$\sum_{k = 0}^{n} k \cdot k!$
を閉形式に表せ。

解説

ステップ1

　 $A (n) = n \cdot n!$ とおくと
$\frac{A (n + 1)}{A (n)} = \frac{(n + 1)^{2}}{n} = \frac{n + 1}{1} \frac{n + 1}{n}$
と表せるので
$a (n) = n + 1, b (n) = 1, c (n) = n$
とおくとよい。

ステップ2

　このとき $x (n)$ の次数は
$d = \deg c (n) - \deg a (n) = 0$
と求まるので $x (n) = K$ とおくと
$\begin{aligned} a (n) x (n + 1) - b (n - 1) x (n) & = K ((n + 1) - 1) \\ = K n \\ = K c (n) \end{aligned}$
より $K = 1$ を得る。

ステップ3

　以上より
$\begin{aligned} T (n) & = \frac{b (n - 1)}{c (n)} x (n) A (n) \\ = \frac{1}{n} \cdot (n \cdot n!) = n! \\ \sum_{k = 0}^{n} A (k) & = T (n + 1) - T (0) \\ = (n + 1)! - 1 \end{aligned}$
を得る。

$\sum_{k = 0}^{n} k!$
は閉形式に表せないことを示せ。

解説

　 $A (n) = n!$ とおくと
$\frac{A (n + 1)}{A (n)} = n + 1$
が成り立つので
$a (n) = n + 1, b (n) = 1, c (n) = 1$
とおくとよい。このとき
$a (n) x (n + 1) - b (n - 1) x (n) = c (n)$
なる多項式 $x (n)$ が存在すればその次数は
$d = \deg c (n) - \deg b (n) = - 1$
となって不適。よって主張を得る。

$\sum_{k = 0}^{n} (\binom{N}{k})$
は閉形式に表せないことを示せ。

解説

　 $A (n) = (\binom{N}{n})$ とおくと
$\frac{A (n + 1)}{A (n)} = \frac{N - n}{n + 1}$
が成り立つので
$a (n) = N - n, b (n) = n + 1, c (n) = 1$
とおくとよい。このとき
$a (n) x (n + 1) - b (n - 1) x (n) = c (n)$
なる多項式 $x (n)$ が存在すればその次数は
$d = \deg c (n) - \deg b (n) = - 1$
となって不適。よって主張を得る。

$\sum_{k = 1}^{n} \frac{1}{k^{N}} (N \geq 1)$
は閉形式に表せないことを示せ。

解説

　 $A (n) = 1 / n^{N}$ とおくと
$\frac{A (n + 1)}{A (n)} = \frac{n^{N}}{(n + 1)^{N}}$
が成り立つので
$a (n) = n^{N}, b (n) = (n + 1)^{N}, c (n) = 1$
とおくとよい。このとき明らかに
$a (n) x (n + 1) - b (n - 1) x (n) = n^{k} (x (n + 1) - x (n)) = 1$
なる多項式 $x (n)$ は存在し得ないので主張を得る。