ご注文はWZですか？

あいさつ

んちゃ！
今回は初心に戻り、Gosperのアルゴリズム、WZ法について概要を述べ
Gosperのアルゴリズムにより、面白い級数を手計算で見つけることが出来る場合が無いか調べていきます。
因みに最後にGosperのアルゴリズムに沿って実際にやなさんがC言語でコーディングしたコードが付いてます。
良かったらローカルで使ってみてください。
自分のための復習も含まれます。
それではよろしくお願いいたします。

前提知識
Gosperのアルゴリズム
WZ法
手計算できる場合を考えたい
補遺：実際のコード

表記

$N_{0} = {0} \cup N$
$C [x]$ は $C$ 係数多項式全体
$C (x) = {\frac{f (x)}{g (x)} | f, g \in C [x] \land g (x) \neq 0}$
$H$ は超幾何項の全体

前提知識

超幾何項(hypergeometric term)

複素数列 ${h_{n}}_{n \in N_{0}} \subset C$ が以下の性質を持つとき、 ${h_{n}}_{n \in N_{0}}$ を超幾何項(hypergeometric term)と呼ぶ。
$\frac{h_{n + 1}}{h_{n}} \in C (n)$

超幾何項の意味

複素数列

{h_{n}}_{n \in N_{0}} \subset C

が超幾何項だとしましょう。すると定義より、以下の事が成り立ちます。

\exists a_{1}, a_{2}, . . ., a_{p}, b_{1}, b_{2}, . . ., b_{q}, z \in C ∖ {0} s . t . \frac{h_{n + 1}}{h_{n}} = \frac{(a_{1} + n) (a_{2} + n) \dots (a_{p} + n)}{(b_{1} + n) (b_{2} + n) \dots (b_{q} + n)} z

つまり、この式を用いると超幾何項は下記の様に書き直せます。

h_{n} = h_{0} \frac{(a_{1})_{n} (a_{2})_{n} \dots (a_{p})_{n}}{(b_{1})_{n} (b_{2})_{n} \dots (b_{q})_{n}} z^{n} (n \in N_{0})

この式は、

h_{0} = 1

として

_{p} F_{q} (a_{1}, a_{2}, . . ., a_{p}; b_{1}, b_{2}, . . ., b_{q}; z)

の第

n

項と一致する事が分かります。
これが、

{h_{n}}_{n \in N_{0}}

が超幾何項と呼ばれる由来となります。

超幾何項の積

超幾何項の積は超幾何項

${h_{n}}_{n \in N_{0}}, {l_{n}}_{n \in N_{0}} \in H$ とする。
$\begin{array}{r} {\begin{cases} \exists f_{1} (n), g_{1} (n) \in C [n] s . t . \frac{h_{n + 1}}{h_{n}} = \frac{f_{1} (n)}{g_{1} (n)} \in C (n) \\ \exists f_{2} (n), g_{2} (n) \in C [n] s . t . \frac{l_{n + 1}}{l_{n}} = \frac{f_{2} (n)}{g_{2} (n)} \in C (n) \end{cases} \end{array}$
$\begin{array}{rcl} \frac{h_{n + 1} l_{n + 1}}{h_{n} l_{n}} & = & \frac{f_{1} (n) f_{2} (n)}{g_{1} (n) g_{2} (n)} \in C (n) \end{array}$

相似

二つの超幾何項 ${h_{n}}_{n \in N_{0}}, {l_{n}}_{n \in N_{0}} \in H$ とする。この時以下の事が成り立つとき $h_{n} ≃ l_{n}$ と書き相似と言う。
$\frac{h_{n}}{l_{n}} \in C (n)$

相似 $≃$ は同値関係を成す。

[1]反射律[2]対称律は略
[3]推移律
超幾何項 ${h_{n}}_{n \in N_{0}}, {l_{n}}_{n \in N_{0}}, {m_{n}}_{n \in N_{0}} \in H$ が次の性質を持つとしましょう。 $h_{n} ≃ l_{n} \land l_{n} ≃ m_{n}$ 。
すると、以下の性質を満たします。
$\begin{array}{r} {\begin{cases} \exists f_{1} (n), g_{1} (n) \in C [n] s . t . \frac{h_{n}}{l_{n}} = \frac{f_{1} (n)}{g_{1} (n)} \\ \exists f_{2} (n), g_{2} (n) \in C [n] s . t . \frac{l_{n}}{m_{n}} = \frac{f_{2} (n)}{g_{2} (n)} \end{cases} \end{array}$
この式から以下の結論が得られます。ゆえに $h_{n} ≃ m_{n}$
$\begin{array}{rcl} \frac{h_{n}}{m_{n}} & = & \frac{h_{n}}{l_{n}} \frac{l_{n}}{m_{n}} \\ = & \frac{f_{1} (n) f_{2} (n)}{g_{1} (n) g_{2} (n)} \in C (n) \end{array}$

相似な超幾何項の和

二つの超幾何項 ${h_{n}}_{n \in N_{0}}, {l_{n}}_{n \in N_{0}} \in H$ が相似であるとする。
すると、(1) ${h_{n} + l_{n}}_{n \in N_{0}}$ は超幾何項。また、(2) $h_{n}, l_{n} \sim h_{n} + l_{n}$

$\begin{array}{r} {\begin{cases} \exists f_{1} (n), g_{1} (n) \in C [n] s . t . \frac{h_{n + 1}}{h_{n}} = \frac{f_{1} (n)}{g_{1} (n)} \in C (n) \\ \exists f_{2} (n), g_{2} (n) \in C [n] s . t . \frac{l_{n + 1}}{l_{n}} = \frac{f_{2} (n)}{g_{2} (n)} \in C (n) \\ \exists f (n), g (n) \in C [n] s . t . \frac{h_{n}}{l_{n}} = \frac{f (n)}{g (n)} \in C (n) \end{cases} \end{array}$
この式を用いると以下の計算ができる。
[(1)]
$\begin{array}{rcl} \frac{h_{n + 1} + l_{n + 1}}{h_{n} + l_{n}} & = & \frac{\frac{h_{n + 1}}{h_{n}} \frac{h_{n}}{l_{n}} + \frac{l_{n + 1}}{l_{n}}}{1 + \frac{h_{n}}{l_{n}}} \\ = & \frac{\frac{f_{1} (n)}{g_{1} (n)} \frac{f (n)}{g (n)} + \frac{f_{2} (n)}{g_{2} (n)}}{1 + \frac{f (n)}{g (n)}} \\ = & \frac{f_{1} (n) g_{2} (n) f (n) + g_{1} (n) f_{2} (n) g (n)}{g_{1} (n) g_{2} (n) g (n) + g_{1} (n) g_{2} (n) f (n)} \in C (n) \end{array}$
[(2)]
相似 $≃$ は同値関係で、 $h_{n} ≃ l_{n}$ なので、 $l_{n} ≃ h_{n} + l_{n}$ のみを示せばよい。
$\frac{h_{n} + l_{n}}{l_{n}} = \frac{f (n) + g (n)}{g (n)} \in C (n)$

Gosperのアルゴリズム

では次にGosperのアルゴリズムについて書きます。
Gosperのアルゴリズムを学ぶ事で、与えられた超幾何項の総和問題を機械的に望遠鏡和にする方法を学ぶ事が出来ます。

ピックアップ！

本節の重要な項目に飛ぶことが出来ます。読み返すときにぜひ使ってください。

Gosperのアルゴリズム前半部分
Gosperのアルゴリズム後半部分

超幾何項 ${h_{n}}_{n \in N_{0}} \in H$ により定まる下記の数列 ${s_{n}}_{n \in N_{0}}$ も超幾何項。
$s_{n} = \sum_{m = 0}^{n} h_{m}$

超幾何項の定義より以下の式が成り立つ。
$\exists f, g \in C [n] s . t . \frac{h_{n + 1}}{h_{n}} = \frac{f (n)}{g (n)}$
[1] $\forall p, q \in N_{0} : h_{n + p} ≃ h_{n + q}$
一般性を損なわないので、 $p > q$ として計算を進める。
$\begin{array}{rcl} \frac{h_{n + p}}{h_{n + q}} & = & \frac{h_{n + p}}{h_{n + p - 1}} \frac{h_{n + p - 1}}{h_{n + p - 2}} \dots \frac{h_{n + q + 1}}{h_{n + q}} \\ = & \frac{f (n + p - 1)}{g (n + p - 1)} \frac{f (n + p - 2)}{g (n + p - 2)} \dots \frac{f (n + q)}{g (n + q)} \\ = & \frac{F (n)}{G (n)} \in C (n) \end{array}$
[2][1]より $h_{1} ≃ h_{2} ≃ \dots ≃ h_{n}$ が分かる。
また帰納的に構成していくことで $s_{n - 1} ≃ h_{n}$ が分かるので、 $s_{n} ≃ s_{n - 1} + h_{n}$ 。
ゆえに $s_{n}$ は超幾何項である事が示された。

the first part of Gosper algorithm

超幾何項 ${h_{n}}_{n \in N_{0}} \in H$ について以下の事か成り立つ。
$\frac{h_{n}}{h_{n - 1}} = \frac{p_{n}}{p_{n - 1}} \frac{q_{n}}{r_{n}} (n \in N_{0})$
ここで、 $p_{n}, q_{n}, r_{n}$ は次の様に定められている。 $p_{n}, q_{n}, r_{n} \in C [n] \land \forall k \in N_{0} : g c d (q_{n}, r_{n + k}) = 1$

[1] ${h_{n}}_{n \in N_{0}}$ は超幾何項なので、以下の式が成り立つ。
$\exists f (n), g (n) \in C [n] s . t . \frac{h_{n}}{h_{n - 1}} = \frac{f (n)}{g (n)}$
[2] $p_{n}^{(1)}, q_{n}^{(1)}, r_{n}^{(1)} \in C [n]$ を用いて以下の様に書けたとします。
$\begin{array}{r} {\begin{cases} f (n) = p_{n}^{(1)} q_{n}^{(1)} \\ g (n) = p_{n - 1}^{(1)} r_{n}^{(1)} \end{cases} \end{array}$
この時、ある最小の自然数 $k_{1} \in N_{0}$ が存在して次式が成立したとしましょう。
$g c d (q_{n}^{(1)}, r_{n + k_{1}}^{(1)}) = s_{n}^{(1)}$
すると以下の式が成り立つ。
$\begin{array}{r} {\begin{cases} \exists q_{n}^{(2)} \in C [n] s . t . q_{n}^{(1)} = s_{n}^{(1)} q_{n}^{(2)} \\ \exists r_{n}^{(2)} \in C [n] s . t . r_{n}^{(1)} = \frac{r_{n}^{(1)}}{r_{n + 1}^{(1)}} \frac{r_{n + 1}^{(1)}}{r_{n + 2}^{(1)}} \dots \frac{r_{n + k - 1}^{(1)}}{r_{n + k}^{(1)}} r_{n + k}^{(1)} = s_{n}^{(1)} \frac{r_{n}^{(1)}}{r_{n + 1}^{(1)}} \frac{r_{n + 1}^{(1)}}{r_{n + 2}^{(1)}} \dots \frac{r_{n + k_{1} - 1}^{(1)}}{r_{n + k_{1}}^{(1)}} r_{n}^{(2)} \end{cases} \end{array}$
ゆえに、以下の式が得られる。
$\begin{array}{rcl} \frac{f (n)}{g (n)} & = & \frac{p_{n}^{(1)} r_{n + 1}^{(1)} r_{n + 2}^{(1)} \dots r_{n + k_{1}}^{(1)}}{p_{n - 1}^{(1)} r_{n}^{(1)} r_{n + 1}^{(1)} \dots r_{n + k_{1} - 1}^{(1)}} \frac{q_{n}^{(2)}}{r_{n}^{(2)}} \end{array}$
そこでさらに次の様に記号を定めましょう。
$p_{n}^{(2)} = p_{n}^{(1)} r_{n + 1}^{(1)} r_{n + 2}^{(1)} \dots r_{n + k_{1}}^{(1)}$
[3]つまり以下の事を繰り返します。
(i)start: $p_{n}^{(1)}, q_{n}^{(1)}, r_{n}^{(1)} \in C [n]$ を適当に定め、次式が成り立つ様にする。
$\begin{array}{r} {\begin{cases} f (n) = p_{n}^{(1)} q_{n}^{(1)} \\ g (n) = p_{n - 1}^{(1)} r_{n}^{(1)} \end{cases} \end{array}$
(ii) $g c d (q_{n}^{(l)}, r_{n + l}^{(l)}) = s_{n}^{(l)} \neq 1$ を満たす最小の自然数 $k_{l}$ を求める。
その様な自然数が存在しない場合は(iv)へ進む。
(iii)次の様な更新を行う。
$p_{n}^{(l + 1)} = r_{n + 1}^{(l)} r_{n + 2}^{(l)} \dots r_{n + k_{1}}^{(l)} p_{n}^{(l)}$
(iv)end:最終的に次の様に置けば、目的が達成される。
$\begin{array}{r} {\begin{cases} p_{n} = p_{n}^{(l)} \\ q_{n} = q_{n}^{(l)} \\ r_{n} = r_{n}^{(l)} \end{cases} \end{array}$
[4][3]の操作は高々有限回で終了する。
理由は、 $q_{n}^{(l)}$ の次数は有限かつ自然数であり、その次数は単調減少であるため。

整数でない複素数に任意の整数を足しても整数でない複素数になる。

[1]虚部が $0$ 出なければ明らかなので、虚部が $0$ 出ない場合は省略
[2]以下虚部 $0$ の場合。つまり実数かつ整数でない場合について本補題が成り立つ事を示す。
過程より、実数かつ整数でない様なもの $r$ は $\exists x \in Z, \exists y \in (0, 1] s . t . r = x + y$ と書ける。
[3]ゆえに $\forall z \in Z : r + z = (x + z) + y \notin Z$ が得られる。

モニックな多項式 $f (n), g (n) \in C [n]$ のそれぞれの根を $a_{1}, a_{2}, . . ., a_{k}, b_{1}, b_{2}, . . ., b_{l}$ とします。
この時、 $\forall i \in {1, 2, . . ., k}, \forall j \in {1, 2, . . ., l} : | a_{i} - b_{j} | \notin N_{0}$ である場合、以下の式が成り立つ。
$\forall N \in N_{0} : g c d (f (n), g (n + N)) = 1$

与えられた条件より
$\begin{array}{r} {\begin{cases} f (n) = (n - a_{1}) (n - a_{2}) \dots (n - a_{k}) \\ g (n) = (n - b_{1}) (n - b_{2}) \dots (n - b_{l}) \end{cases} \end{array}$
ゆえに任意の自然数に対して以下の事が成り立つ事が分かる。
$g (n + N) = {n - (b_{1} - N)} {n - (b_{2} - N)} \dots {n - (b_{l} - N)}$
そこで、 $f (n), g (n + N)$ が互いに素である事と双方が同一の根を持たない事は同値なので、結局 $\forall i \in {1, 2, . . ., k}, \forall j \in {1, 2, . . ., l} : | a_{i} + N - b_{j} | \neq 0$ を示せばよい。
仮定より、 $\forall i \in {1, 2, . . ., k}, \forall j \in {1, 2, . . ., l} : a_{i} - b_{j} \in C ∖ Z$ なので補題6より $\forall N \in N_{0} \subset Z : \forall i \in {1, 2, . . ., k}, \forall j \in {1, 2, . . ., l} : a_{i} + N - b_{j} \in C ∖ Z$ 。
これから証明が完了された。

超幾何項 ${h_{n}}_{n \in N_{0}} {l_{n}}_{n \in N_{0}} \in H$ が $\forall n \in N_{0} : l_{n + 1} - l_{n} = h_{n}$ この時下記の事が成り立つ。

$\exists ξ_{n} \in C (n) s . t . l_{n} = ξ_{n} h_{n}$
$\frac{h_{n + 1}}{h_{n}} ξ_{n + 1} - ξ_{n} = 1$
$\exists p_{n}, q_{n}, r_{n} \in C (n) s . t . \forall N \in N_{0} : g c d (q_{n}, r_{n + N}) = 1 : \frac{h_{n + 1}}{h_{n}} = \frac{p_{n + 1}}{p_{n}} \frac{q_{n + 1}}{r_{n + 1}}$ が成り立つ事が定理5により分かっている。この $p_{n}, q_{n}, r_{n}$ を用いて $ξ_{n} = \frac{r_{n}}{p_{n}} η_{n}$ の様に置き直せば次の式が得られます。 $q_{n + 1} η_{n + 1} - r_{n} η_{n} = p_{n}$

[1]
$\begin{array}{rcl} l_{n + 1} - l_{n} & = & l_{n} (\frac{l_{n + 1}}{l_{n}} - 1) \\ = & h_{n} \end{array}$
超幾何項の定義より、 $\frac{l_{n + 1}}{l_{n}} \in C (n)$ なので、 $ξ_{n} = \frac{1}{\frac{l_{n + 1}}{l_{n}} - 1} \in C (n)$ が成り立つ。
この式を用いると下記の式が得られます。
$\exists ξ_{n} \in C (n) s . t . l_{n} = ξ_{n} h_{n}$
[2]この $ξ_{n}$ は整理すると以下の式が得られます。
$\forall n \in N_{0} : \frac{h_{n + 1}}{h_{n}} ξ_{n + 1} - ξ_{n} = 1$
[3]定理5より下記の式を得ることが出来る。
$\exists p_{n}, q_{n}, r_{n} \in C [n] s . t . \forall N \in N_{0} : g c d (q_{n}, r_{n + N}) = 1 : \frac{h_{n}}{h_{n - 1}} = \frac{p_{n}}{p_{n - 1}} \frac{q_{n}}{r_{n}}$
また、 $ξ_{n} = \frac{r_{n}}{p_{n}} η_{n}$ の様に置き直すと次式が成り立つ。
$\begin{array}{rcl} \frac{h_{n + 1}}{h_{n}} ξ_{n + 1} - ξ_{n} & = & \frac{p_{n + 1}}{p_{n}} \frac{q_{n + 1}}{r_{n + 1}} \frac{r_{n + 1}}{p_{n + 1}} η_{n + 1} - \frac{r_{n}}{p_{n}} η_{n} \\ = & \frac{q_{n + 1}}{p_{n}} η_{n + 1} - \frac{r_{n}}{p_{n}} η_{n} \\ = & 1 \end{array}$
それゆえに、下記の式を得る。
$q_{n + 1} η_{n + 1} - r_{n} η_{n} = p_{n}$

ここまでの変形でなぜこのような式変形を行うのだろうと疑問に思った方々もいらっしゃると思います。
その疑問を解消してくれるのが次の定理です。

the second half of Gosper algorithm

数列 ${η_{n}}_{n \in N_{0}}$ が
$p_{n}, q_{n}, r_{n} \in C [n], \forall N \in N_{0} : g c d (q_{n}, r_{n + N}) = 1$ に対して定まる下記の漸化式を満たしているとする。
$q_{n + 1} η_{n + 1} - r_{n} η_{n} = p_{n}$
すると実は、 $η_{n} \in C [n]$ となる！

$η_{n}$ が有理関数ではなく多項式になると驚きの定理です。
この定理より、 $d e g (p_{n}) = k$ であれば $η_{n} = \sum_{a = 1}^{k} A_{a} n^{a}$ の様に置いて $A_{0}, A_{1}, . . ., A_{k}$ を探せばいいのです。
Gosperさん凄いですよね。
では、この定理を証明しましょう。

まず、 $η_{n} \in C (n)$ である事は分かりますので $\exists f (n), g (n) \in C [n] s . t . g c d (f (n), g (n)) = 1 \land η_{n} = \frac{f (n)}{g (n)}$ と書けます。
示すべきことは、 $g (n) = c o n s t .$ です。
[0] $g (n) = c o n s t .$ の場合は示す事はありません。
[1]そこで $g (n) \neq c o n s t .$ であるとします。するとこれを代入する事で下記の式を得ます。
$q_{n + 1} f (n + 1) g (n) - r_{n} f (n) g (n + 1) = p_{n} g (n) g (n + 1)$
また、明らかに $\exists N \in N_{0} s . t . g c d (g (n), g (n + N)) = u (n) \neq 1$ が成り立ちます(少なくともN=0で成り立つ)から。その様な $N$ の最大のものを $N^{*}$ とします。
右辺は $g (n + 1)$ の倍数ですから、両辺は $u (n + 1)$ で割れます。
つまり次の事が成り立つ事が分かります。
$u (n + 1) | q_{n + 1}$
さらに、次の式から $u (n + 1) | r_{n + N}$ が得られます。
$q_{n + N + 1} f (n + N + 1) g (n + N) - r_{n + N} f (n + N) g (n + N + 1) = p_{n + N} g (n + N) g (n + N + 1)$
しかし矛盾しています。
なぜなら、 $\forall N \in N_{0} : g c d (q_{n}, r_{n + N}) = 1$ としたからです。
この矛盾は、 $g (n) \neq c o n s t .$ とした事から起きました。
ゆえに、 $g (n) = c o n s t .$ 出なければなりません！

上述のGosperのアルゴリズムに従いC言語やpythonなどでコーディングを行い、実行する事で $l_{n}$ を構成出来れば望遠鏡和により命題4の $s_{n}$ は次の様に書ける事が分かります。
$s_{n} = l_{n + 1} - l_{0}$

この方程式を解く方法は次の様です。
多項式

p = \sum_{k = 0}^{m} p_{k} x^{k}

に多項式

q = \sum_{k = 0}^{n} q_{k} x^{k}

をかけて出来る多項式

r = \sum_{k = 0}^{m + n} r_{k} x^{k}

との間には次の式が成り立つ事を用います。

(\begin{matrix} q_{0} & 0 & 0 & 0 & \dots & \dots & 0 \\ q_{1} & q_{0} & 0 & 0 & \dots & \dots & 0 \\ \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ 0 & \dots & q_{n} & \dots & q_{0} & \dots & 0 \end{matrix}) (\begin{matrix} p_{0} \\ p_{1} \\ ⋮ \\ p_{n} \end{matrix}) = (\begin{matrix} r_{0} \\ r_{1} \\ ⋮ \\ r_{m + n} \end{matrix})

この式を用いて連立方程式を立てればよいです。

WZ法

WZ法とはHerbert WilfとDoron Zeilbergerにより見つけられたものです。
この方法の全貌を見るために次の様な二変数の超幾何項に関する恒等式を考えます。

WZ的組

二つの二変数の超幾何項 $F (n, k), G (n, k)$ が次の恒等式を満たす時、WZ的組と呼ぶ。
$\forall n, k \in N_{0} : F (n + 1, k) - F (n, k) = G (n, k + 1) - G (n, k)$

実はこのWZ的組である事が本質的です。
それでは、核心をつきましょう。

WZ-method

WZ的組 $F (n, k), G (n, k)$ が $\forall k \in N_{0} : F (0, k) = 0$ を満たし、なおかつ $\forall k \in N_{0} : lim_{n \to \infty} F (n, k) = 0$ が成り立つ時以下の式が成り立つ。
$\forall k \in N_{0} : \sum_{n \in N_{0}} G (n, k) = c o n s t .$

まず $g (k) : = \sum_{n \in N_{0}} G (n, k)$ と置きましょう。
WZ的組の定義を用いると
$F (n + 1, k) = \sum_{n = 0}^{n} G (n, k + 1) - \sum_{n = 0}^{n} G (n, k)$
が成り立つ事が、 $n$ について $0$ から $n$ まで総和を取れば分かります。
ゆえに、 $n \to \infty$ として下記の式が得られます。
$\forall k \in N_{0} : g (k) = g (k + 1)$
つまり、 $g (0) = g (1) = \dots = g (k) = \dots = c o n s t .$ が得られるので本定理は証明された。

しかし、これだけだとそもそもWZ的組を見つけるにはどうすればいいか分からないのでもう少し踏み込んでみましょう。
まず、多項式

Q (n, k), R (n, k) \in C [n, k]

を

\forall N \in N : g c d (Q (n, k), R (n + N, k)) = 1

が成り立つ様に定めます。
そして、適当な多項式

η (n, k) \in C (n, k)

を定め、次の様にして多項式

P (n, k) \in C (n, k)

を作ります。

Q (n + 1, k) η (n + 1, k) - R (n, k) η (n, k) = P (n, k)

そして次の計算を行います。

\begin{array}{r} {\begin{cases} ξ (n, k) = \frac{R (n, k)}{P (n, k)} η (n, k) \\ H (n, k) = \frac{P (n, k) Q (n, k) Q (n - 1, k) \dots Q (1, k)}{P (0, k) R (n, k) R (n - 1, k) \dots R (1, k)} \\ F (n, k) = ξ (n, k) H (n, k) \end{cases} \end{array}

すると自動的に

F (n + 1, k) - F (n, k) = H (n, k)

を満たす超幾何項

F (n, k), H (n, k)

を構成出来ます。後は、

H (n, k)

の

k

についてGosperのアルゴリズムに沿って計算を進め

G (n, k)

を求め

H (n, k) = G (n, k + 1) - G (n, k)

を構成すればWZ的組を構成出来る。
$H (n, k)$ は一般的に $k$ についてGosperのアルゴリズムを適用しても解を持たないケースも存在するため、 $G$ を構成できない事もある事に注意。

これから、この分野で研究をする場合は以下の方法を探すのがよさそうです。

Gosperアルゴリズムで $G$ を求める事が可能な $Q, R, η$ を定める方法
Gosperアルゴリズムを使用しないでも $G$ を求める方法

手計算できる場合を考えたい

まずは一番簡単な例で考えます。

和： $S_{N} = \sum_{n = 1}^{N} 2^{n} n^{2}$ を求めてください。

0.まずは $h_{n} = 2^{n} n^{2}$ が超幾何項である事を確認しましょう。
$\frac{h_{n + 1}}{h_{n}} = \frac{(n + 1)^{2}}{n^{2}} \frac{2}{1}$

Gosper変形：しかし、これは既に最初から適切な形になっているので今回は不要。
Gosper方程式を解く：下記の様に記号を定めます。
$\begin{array}{r} {\begin{cases} l_{n} = ξ_{n} 2^{n} n^{2} \\ ξ_{n} = \frac{1}{n^{2}} η_{n} \\ 2 η_{n + 1} - η_{n} = n^{2} \end{cases} \end{array}$
$η_{n} = n^{2} + a n + b$ と置いて計算すると $a = - 4, b = 6$ が成り立つ事が分かります。
ゆえに、以下の数列が得られます。
$l_{n} = 2^{n} (n^{2} - 4 n + 6) (n \in N_{0})$
$l_{n}$ を用いると下記の結論が得られる。
$\begin{array}{rcl} S_{N} & = & l_{N + 1} - l_{1} \\ = & 2^{N + 1} (N^{2} - 2 N + 3) - 6 \end{array}$

以下の三つの多項式について
$\begin{array}{r} {\begin{cases} p_{n} = 3 n^{3} + 8 n^{2} + \frac{29}{3} n + 3 \\ q_{n} = 3 n^{2} \\ r_{n} = n - \frac{2}{3} \end{cases} \end{array}$
次の事に答えよ。
0. $\forall N \in N_{0} : g c d (q_{n}, r_{n + N}) = 1$ が成り立つ事を示してください。
1. $q_{n + 1} η_{n} - r_{n} η_{n} = p_{n}$ の解は $η_{n} = n$ である事を証明してください。
2.これから、 $ξ_{n} = \frac{r_{n}}{p_{n}} η_{n}$ とおき、 $\frac{h_{n + 1}}{h_{n}} = \frac{p_{n + 1}}{p_{n}} \frac{q_{n + 1}}{r_{n + 1}}, l_{n} = ξ_{n} h_{n}$ が成り立つ様に数列 $l_{n}, h_{n}$ を定めると $l_{n + 1} - l_{n} = h_{n}$ が成り立っている事を示してください。
ただし、 $h_{0} = 1$ とします。
3.最後に $\sum_{n = 1}^{N} h_{n}$ を求めてください。

0. $q_{n}, r_{n}$ のそれぞれの根は $0, 0; \frac{2}{3}$ です。という事は、 $| 0 - \frac{2}{3} | = \frac{2}{3} \notin N_{0}$ ですから命題7より $\forall N \in N_{0} : g c d (q_{n}, r_{n + N}) = 1$ が示された。
1.0.より与えられた方程式はGosper方程式なので解は多項式の形を取る。
そこで、 $η_{n} = A n + B$ の様な形を仮定できます。
代入して $A, B$ を求めると $A = 1, B = 0$ が得られるので証明完了。
2.1.の計算より $ξ_{n} = \frac{n (n - \frac{2}{3})}{3 n^{3} + 8 n^{2} + \frac{29}{3} n + 3}$
また、下記の様に計算できます。
$\begin{array}{rcl} h_{n} & = & \frac{p_{n} q_{n} q_{n - 1} \dots q_{1}}{p_{0} r_{n} r_{n - 1} \dots r_{1}} \\ = & \frac{3^{n - 1} (3 n^{3} + 8 n^{2} + \frac{29}{3} n + 3) (n!)^{2}}{(\frac{1}{3})_{n}} \end{array}$
この計算から、が得られます。
$\begin{array}{rcl} l_{n} & = & ξ_{n} h_{n} \\ = & \frac{3^{n - 1} n (n - \frac{2}{3}) (n!)^{2}}{(\frac{1}{3})_{n}} \end{array}$
4.最後の和に関しては次の様になります。
$\begin{array}{rcl} \sum_{n = 1}^{N} h_{n} & = & l_{N + 1} - l_{1} \\ = & \frac{3^{N} (N + \frac{1}{3}) (N + 1) {(N + 1)!}^{2}}{(\frac{1}{3})_{N + 1}} - 1 \end{array}$
つまり、次の様な計算が出来る事を意味しています。
$\sum_{n = 1}^{N} \frac{3^{n - 1} (3 n^{3} + 8 n^{2} + \frac{29}{3} n + 3) n!}{(\frac{1}{3})_{n}} = \frac{3^{N} (N + \frac{1}{3}) (N + 1) {(N + 1)!}^{2}}{(\frac{1}{3})_{N + 1}} - 1$

ここでの計算から分かりますように、 $\forall N \in N : g c d (q_{n}, r_{n + N}) = 1$ を満たす $q_{n}, r_{n}$ を先に定めましてそこから $η_{n}$ を決め、その後に $p_{n}$ を求める事で面白い級数の公式を構成できます。
残念ながら、一般の場合Gosperの方程式は解を持つとは限りません。
しかし、この構成法ならいつでも可能です。
でも不満です。だって、この方法だと例えば $ζ (2)$ の加速級数すら導出できません。
ではどうすればいいでしょうか？
パラメータの個数を増やします。

次の様な二変数の多項式を考える。
$\begin{array}{r} {\begin{cases} Q (n, k) = n + k + 1 \\ R (n, k) = n^{2} k - \frac{1}{2} \end{cases} \end{array}$
この時、次の問題を解いてください。
1. $n$ を主変数とした時、 $\forall N \in N : g c d (Q (n, k), R (n + N, k)) = 1$ が成り立つ。
2. $η (n, k) = n^{3}$ とおき次の様な $P (n, k)$ を求めよ。
$Q (n + 1, k) η (n + 1, k) - R (n, k) η (n, k) = P (n, k)$
3. $ξ (n, k) = \frac{R (n, k)}{P (n, k)} η (n, k)$ を求めよ。
4. $H (n, k) = \frac{P (n, k) Q (n, k) Q (n - 1, k) \dots Q (1, k)}{P (0, k) R (n, k) R (n - 1, k) \dots R (1, k)}$
5. $F (n, k) = ξ (n, k) H (n, k)$ とおくと $F (n + 1, k) - F (n, k) = H (n, k)$ を満たします。これを用いて $\sum_{n = 1}^{N - 1} H (n, k)$ を計算してください。

1.まず次の様に計算します。
$\begin{array}{rcl} R (n + N, k) & = & (n + N)^{2} k - \frac{1}{2} \\ = & n^{2} k + 2 N n k + N^{2} k - \frac{1}{2} \end{array}$
そして $R (n + N, k)$ を $Q (n, k)$ で $n$ を主変数として割ります。すると余りは次の様になります。
$k^{3} + 2 (1 - N) k^{2} + (N - 1)^{2} k - \frac{1}{2} \neq 0$
ゆえに $\forall N \in N : g c d (Q (n, k)) = 1$ を得る。
2.計算するだけです。
$\begin{array}{rcl} Q (n + 1, k) η (n + 1, k) - R (n, k) η (n, k) & = & (n + k + 2) (n + 1)^{3} - (n^{2} k - \frac{1}{2}) n^{3} \\ = & - n^{5} k + n^{4} + (k + \frac{11}{2}) n^{3} + 3 (k + 3) n^{2} + (3 k + 7) n + k + 2 \end{array}$
つまり
$P (n, k) = - n^{5} k + n^{4} + (k + \frac{11}{2}) n^{3} + 3 (k + 3) n^{2} + (3 k + 7) n + k + 2$
3.以降は定義に従って計算しましょう。
$\begin{array}{rcl} ξ (n, k) & = & \frac{R (n, k)}{P (n, k)} η (n, k) \\ = & \frac{n^{5} k + \frac{1}{2} n^{3}}{- n^{5} k + n^{4} + (k + \frac{11}{2}) n^{3} + 3 (k + 3) n^{2} + (3 k + 7) n + k + 2} \end{array}$
4.
$\begin{array}{rcl} H (n, k) & = & \frac{P (n, k) Q (n, k) Q (n - 1, k) \dots Q (1, k)}{P (0, k) R (n, k) R (n - 1, k) \dots R (1, k)} \\ = & \frac{{- n^{5} k + n^{4} + (k + \frac{11}{2}) n^{3} + 3 (k + 3) n^{2} + (3 k + 7) n + k + 2} (k + 2)_{n}}{(k + 2) k^{n} (1 - \frac{1}{\sqrt{2 k}})_{n} (1 + \frac{1}{\sqrt{2 k}})_{n}} \end{array}$
5.
$\begin{array}{rcl} F (n, k) & = & ξ (n, k) H (n, k) \\ = & \frac{(n^{5} k + \frac{1}{2} n^{3}) (k + 2)_{n}}{(k + 2) k^{n} (1 - \frac{1}{\sqrt{2 k}})_{n} (1 + \frac{1}{\sqrt{2 k}})_{n}} \end{array}$
より
$\begin{array}{rcl} \sum_{n = 1}^{N - 1} H (n, k) & = & F (N, k) - F (1, k) \\ = & \frac{{N^{5} k + \frac{1}{2} N^{3}} (k + 2)_{N}}{(k + 2) k^{N} (1 - \frac{1}{\sqrt{2 k}})_{N} (1 + \frac{1}{\sqrt{2 k}})_{N}} - \frac{k + \frac{1}{2}}{k - \frac{1}{2}} \end{array}$
この例は次の様な事を意味しています。
$\sum_{n = 1}^{N - 1} \frac{{- n^{5} k + n^{4} + (k + \frac{11}{2}) n^{3} + 3 (k + 3) n^{2} + (3 k + 7) n + k + 2} (k + 2)_{n}}{(k + 2) k^{n} (1 - \frac{1}{\sqrt{2 k}})_{n} (1 + \frac{1}{\sqrt{2 k}})_{n}} = \frac{{N^{5} k + \frac{1}{2} N^{3}} (k + 2)_{N}}{(k + 2) k^{N} (1 - \frac{1}{\sqrt{2 k}})_{N} (1 + \frac{1}{\sqrt{2 k}})_{N}} - \frac{k + \frac{1}{2}}{k - \frac{1}{2}}$

上の計算は自信が無いので一応予想でとどめておきます。
因みに、 $G (n, k)$ を構成するのは流石に手で計算できる範囲を超えているので省略いたします。(👈不可能かもしれない)

任意の自然数 $k \in N$ に対して以下の式が成り立ちます。
$\sum_{n = 1}^{N - 1} \frac{{- n^{5} k + n^{4} + (k + \frac{11}{2}) n^{3} + 3 (k + 3) n^{2} + (3 k + 7) n + k + 2} (k + 2)_{n}}{(k + 2) k^{n} (1 - \frac{1}{\sqrt{2 k}})_{n} (1 + \frac{1}{\sqrt{2 k}})_{n}} = \frac{{N^{5} k + \frac{1}{2} N^{3}} (k + 2)_{N}}{(k + 2) k^{N} (1 - \frac{1}{\sqrt{2 k}})_{N} (1 + \frac{1}{\sqrt{2 k}})_{N}} - \frac{k + \frac{1}{2}}{k - \frac{1}{2}}$