文献あり

超幾何数列の基礎4：二重数列の総和

400

はじめに

　この記事では前回の記事に引き続き超幾何数列の基本事項についてまとめていきます。
　前回までの記事では一変数の超幾何数列に注目して閉形式の求め方や漸化式の解き方について解説してきましたが、今回からは二変数の超幾何数列に焦点を当てていきます。

二変数の超幾何数列

超幾何数列

　二重数列 $F (n, k)$ が超幾何数列であるとは
$\frac{F (n + 1, k)}{F (n, k)}, \frac{F (n, k + 1)}{F (n, k)}$
がそれぞれ $n, k$ についての有理関数となることを言う。

proper

　超幾何数列 $F (n, k)$ がproperであるとは、ある多項式 $P (n, k)$ およびある定数
$a_{j}, b_{j}, a_{j}^{'}, b_{j}^{'} \in Z, c_{j}, c_{j}^{'}, x, y \in C$
が存在して
$F (n, k) = P (n, k) \frac{\prod_{j = 1}^{s} Γ (a_{j} n + b_{j} k + c_{j})}{\prod_{j = 1}^{t} Γ (a_{j}^{'} n + b_{j}^{'} k + c_{j}^{'})} x^{n} y^{k}$
と表せることを言う。

　なおある $j$ に対し $a_{j} n + b_{j} k + c_{j}$ が $0$ 以下の整数となるような $(n, k)$ に対して $F (n, k)$ は定義されない(ill-definedである)ものとし、またある $j$ に対し $a_{j}^{'} n + b_{j}^{'} k + c_{j}^{'}$ が $0$ 以下の整数となるような $(n, k)$ に対しては $F (n, k) = 0$ と定めます。例えば二項係数
$(\binom{n}{k}) = \frac{n!}{k! (n - k)!} = \frac{Γ (n + 1)}{Γ (k + 1) Γ (n - k + 1)}$
は $n < 0$ に対しては定義されず、 $k < 0$ または $n < k$ においては $0$ と定まります。
　ちなみに $(x)_{m}$ をポッホハマー記号
$(x)_{m} = \frac{Γ (x + m)}{Γ (x)} = {\begin{cases} x (x + 1) \dots (x + m - 1) & (m \geq 0) \\ \frac{1}{(x - 1) \dots (x - | m |)} & (m < 0) \end{cases}$
とするとproperな超幾何数列は
$F (n, k) = Q (n, k) \frac{\prod_{j = 1}^{s} (c_{j})_{a_{j} n + b_{j} k}}{\prod_{j = 1}^{t} (c_{j}^{'})_{a_{j}^{'} n + b_{j}^{'} k}} x^{n} y^{k}$
のようにも表せます。

基本定理

　本題に入っていく前にまずはproperな超幾何数列が満たす漸化的性質について紹介しておきましょう。

Sister Celine's Method

　properな超幾何数列 $F (n, k)$ は $k$ に依らない漸化式を満たす。
　つまりある(どれか一つは $0$ ではない)多項式 $a_{i, j} (n)$ が存在して
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) F (n + i, k + j) = 0$
が成り立つ。さらにこの $I, J$ (の上界)として
$\begin{aligned} I & = \sum_{j = 1}^{s} | b_{j} | + \sum_{j = 1}^{t} | b_{j}^{'} | \\ J & = 1 + \deg P + I (\sum_{j = 1}^{s} | a_{j} | + \sum_{j = 1}^{t} | a_{j}^{'} | - 1) \end{aligned}$
と取れる(ただし $\deg$ は $k$ についての次数を考えるものとした)。

証明

方針

　 $I, J$ を任意に取り $a_{i, j} (n) \in C [n]$ を未知数とする線形方程式
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) F (n + i, k + j) = 0$
を考えたとき、両辺を $F (n, k)$ で割ることでこの方程式はある多項式 $ν_{i, j} (n, k), δ_{i, j} (n, k)$ を用いて
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) \frac{ν_{i, j} (n, k)}{δ_{i, j} (n, k)} = 0$
と表せ、また $δ_{i, j} (n, k)$ の最小公倍多項式を $Δ (n, k)$ とおくと
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) ν_{i, j} (n, k) \frac{Δ (n, k)}{δ_{i, j} (n, k)} = 0$
という多項式の恒等式に帰着できる。
　ここでこの左辺の $k$ についての次数を $d$ とおくと係数比較によってこれは $d + 1$ 本の方程式に分解でき、またこの方程式の未知数の個数は $(I + 1) (J + 1)$ 個であるので十分大きい $I, J$ に対し
$d + 1 < (I + 1) (J + 1)$
が成り立つことを示せばよい(一般に方程式の本数より未知数の個数の方が多い線形方程式は非自明な解を持つことが知られている)。

最小公倍多項式

　以下簡単のため $m \geq 0$ に対し
$\begin{aligned} rf (x, m) & = (x)_{m} = x (x + 1) \dots (x + m - 1) \\ ff (x, m) & = \frac{1}{(x)_{- m}} = (x - 1) \dots (x - m) \end{aligned}$
と定める( $rf, ff$ は上昇階乗(rising factorial)と下降階乗(falling factorial)の頭文字を取っている)。
　このとき
$\frac{F (n + i, k + j)}{F (n, k)} = \frac{ν_{i, j} (n, k)}{δ_{i, j} (n, k)}$
と置いていたので $ν_{i, j}, δ_{i, j}$ は
$\begin{aligned} ν_{i, j} (n, k) & = P (n + i, k + j) x^{i} y^{j} & \times \prod_{\begin{array}{c} l = 1 \\ a_{l} i + b_{l} j > 0 \end{array}}^{s} rf (a_{l} n + b_{l} k + c_{l}, a_{l} i + b_{l} j) \\ \times \prod_{\begin{array}{c} l = 1 \\ a_{l}^{'} i + b_{l}^{'} j < 0 \end{array}}^{t} ff (a_{l}^{'} n + b_{l}^{'} k + c_{l}^{'}, | a_{l}^{'} i + b_{l}^{'} j |) \\ δ_{i, j} (n, k) & = P (n, k) & \times \prod_{\begin{array}{c} l = 1 \\ a_{l} i + b_{l} j < 0 \end{array}}^{s} ff (a_{l} n + b_{l} k + c_{l}, | a_{l} i + b_{l} j |) \\ \times \prod_{\begin{array}{c} l = 1 \\ a_{l}^{'} i + b_{l}^{'} j > 0 \end{array}}^{t} rf (a_{l}^{'} n + b_{l}^{'} k + c_{l}^{'}, a_{l}^{'} i + b_{l}^{'} j) \end{aligned}$
のように表せる(ただし $ν_{i, j} / δ_{i, j}$ は既約分数とは限らない)。ここで実数 $X$ に対し
$X^{+} = max {X, 0}, X^{-} = max {- X, 0}$
と定めたとき
$\begin{aligned} max {α i + β j ∣ 0 \leq i \leq I, 0 \leq j \leq J} & = α^{+} I + β^{+} J \\ min {α i + β j ∣ 0 \leq i \leq I, 0 \leq j \leq J} & = - (α^{-} I + β^{-} J) \end{aligned}$
が成り立つことに注意すると $δ_{i, j}$ の最小公倍多項式は
$\begin{aligned} Δ (n, k) & = P (n, k) & \times \prod_{l = 1}^{s} ff (a_{l} n + b_{l} k + c_{l}, a_{l}^{-} i + b_{l}^{-} j) \\ \times \prod_{l = 1}^{t} rf (a_{l}^{'} n + b_{l}^{'} k + c_{l}^{'}, (a_{l}^{'})^{+} i + (b_{l}^{'})^{+} j) \end{aligned}$
と求まる。

次数の評価

　このとき
$\begin{aligned} \deg ν_{i, j} (n, k) & \leq \deg P + & \sum_{l = 1}^{s} (a_{l}^{+} I + b_{l}^{+} J) + \sum_{l = 1}^{t} ((a_{l}^{'})^{-} I + (b_{l}^{'})^{-} J) \\ \deg (\frac{Δ (n, k)}{δ_{i, j} (n, k)}) & \leq & \sum_{l = 1}^{s} (a_{l}^{-} I + b_{l}^{-} J) + \sum_{l = 1}^{t} ((a_{l}^{'})^{+} I + (b_{l}^{'})^{+} J) \end{aligned}$
および $X^{+} + X^{-} = | X |$ に注意すると
$\deg (ν_{i, j} (n, k) \frac{Δ (n, k)}{δ_{i, j} (n, k)}) \leq \deg P + \sum_{l = 1}^{s} (| a_{l} | I + | b_{l} | J) + \sum_{l = 1}^{t} (| a_{l}^{'} | I + | b_{l}^{'} | J)$
が成り立つことがわかる。
　したがって $d$ は $I, J$ についての一次関数程度の大きさであり、 $I, J$ が十分大きいときこれは $(I + 1) (J + 1) - 1$ より小さいことがわかる。特に
$A = \sum_{l = 1}^{s} | a_{l} | + \sum_{l = 1}^{t} | a_{l}^{'} |, B = \sum_{l = 1}^{s} | b_{l} | + \sum_{l = 1}^{t} | b_{l}^{'} |$
とおき
$I = B, J = 1 + \deg P + (A - 1) I$
とすると
$\begin{aligned} d + 1 & \leq 1 + \deg P + A I + B J \\ = I + J + I J \\ = (I + 1) (J + 1) - 1 \\ < (I + 1) (J + 1) \end{aligned}$
と所望の不等式が満たされることがわかる。

　なおproperという条件は
$\frac{F (n + i, n + j)}{F (n, k)} = \frac{ν_{i, j} (n, k)}{δ_{i, j} (n, k)}$
とおいたとき $δ_{i, j}$ の最小公倍多項式 $Δ$ に対し
$ν_{i, j} (n, k) \frac{Δ (n, k)}{δ_{i, j} (n, k)}$
の $k$ についての次数を推定するためにのみ利用しており、一般の超幾何数列に対しても上と同様の方針で
$d + 1 < (I + 1) (J + 1)$
を満たすような $I, J$ の取り方があれば
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) F (n + i, k + j) = 0$
という漸化式が存在することがわかります。
　ちなみに $I, J$ の上界について次のような事実も知られています(証明は気が向いたら書きます)。

　properな超幾何数列 $F (n, k)$ が多項式部分を持たない、つまり
$F (n, k) = \frac{\prod_{j = 1}^{s} Γ (a_{j} n + b_{j} k + c_{j})}{\prod_{j = 1}^{t} Γ (a_{j}^{'} n + b_{j}^{'} k + c_{j}^{'})} x^{n} y^{k}$
と表されるとき、定理1における $I, J$ の上界として
$\begin{aligned} I & = \sum_{j = 1}^{t} (b_{j}^{'})^{-} + \sum_{j = 1}^{s} b_{j}^{+} + {(\sum_{j = 1}^{t} b_{j}^{'} - \sum_{j = 1}^{s} b_{j})}^{+} \\ J & = 1 + I (\sum_{j = 1}^{t} (a_{j}^{'})^{-} + \sum_{j = 1}^{s} a_{j}^{+} + {(\sum_{j = 1}^{t} a_{j}^{'} - \sum_{j = 1}^{s} a_{j})}^{+} - 1) \end{aligned}$
と取れる。ただし実数 $X$ に対して
$X^{+} = max {X, 0}, X^{-} = max {- X, 0}$
と定めるものとした。

Zeilberger's Method

　properな超幾何数列 $F (n, k)$ に対して、ある(どれか一つは $0$ でない)多項式 $A_{i} (n)$ および $G (n, k) / F (n, k)$ を $n, k$ についての有理関数とするような数列 $G (n, k)$ が存在して
$\sum_{i = 0}^{I} A_{i} (n) F (n + i, k) = G (n, k + 1) - G (n, k)$
が成り立つ。

証明

構成法

　 $F$ がproperであることから
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) F (n + i, k + j) = 0$
なる多項式 $a_{i, j} (n)$ が取れ、これに対し多項式 $P$ を
$P (x, y, z) = \sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (x) y^{i} z^{j}$
によって定める。また $N, K$ をそれぞれ $n, k$ についての前進作用素、つまり数列 $f (n, k)$ に対して
$N f (n, k) = f (n + 1, k), K f (n, k) = f (n, k + 1)$
と定めると
$P (n, N, K) F (n, k) = 0$
が成り立つことに注意する。
　いま $P$ を $z$ の多項式として $(1 - z)$ で割ることで
$P (x, y, z) = P (x, y, 1) + (1 - z) Q (x, y, z)$
と表すと
$P (n, N, 1) F (n, k) = (K - 1) Q (n, N, K) F (n, k)$
が成り立つので
$G (n, k) = Q (n, N, K) F (n, k), A_{i} (n) = \sum_{j = 0}^{J} a_{i, j} (n)$
とおくと
$\sum_{i = 0}^{I} A_{i} (n) F (n + i, k) = G (n, k + 1) - G (n, k)$
を得る。また $G$ の取り方から $G (n, k) / F (n, k)$ は $n, k$ についての有理関数となる。

非自明性

　次に $P (x, y, 1) \neq 1$ を満たすような多項式 $P (x, y, z)$ が存在することを示す。
　いま $P (n, N, K) F (n, k) = 0$ を満たすような多項式 $P (x, y, z) \neq 0$ であって $z$ についての次数が最小となるようなものを取る。このとき $P (x, y, 1) = 0$ が成り立つとすると
$P (n, N, 1) F (n, k) = 0 = G (n, k + 1) - G (n, k)$
より $G$ は $k$ に依らない数列となり、またこれは超幾何数列であったことからある $0$ でない多項式 $B_{0} (n), B_{1} (n)$ が存在して
$B_{1} (n) G (n + 1, k) - B_{0} (n) G (n, k) = 0$
が成り立つ。
　したがって $R (n, N) = B_{1} (n) N - B_{0} (n)$ とおくと
$R (n, N) G (n, k) = R (n, N) Q (n, N, K) F (n, k) = 0$
つまり
$P^{'} (x, y, z) = R (x, y) Q (x, y, z)$
は $P^{'} (n, N, K) F (n, k) = 0$ を満たす多項式となるが
$P (x, y, z) = (1 - z) Q (x, y, z)$
であったことから $P^{'}$ は $z$ について $P$ よりも次数が低い多項式であり、これは $P$ の取り方に矛盾。よって $P (x, y, 1) \neq 0$ を得る。

　この結果もproperという条件は定理1のような漸化式
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) F (n + i, k + j) = 0$
の存在を保証するためにのみ利用しており、一般の超幾何数列に対してもこのような漸化式が存在すれば
$\sum_{i = 0}^{I} A_{i} (n) F (n + i, k) = G (n, k + 1) - G (n, k)$
を満たすような数列 $G$ を構成することができます。

二重数列の総和

　さて第一回の記事でも言及したように我々が(proper) 超幾何数列を考える上で関心が高いのはその総和
$f (n) = \sum_{k} F (n, k)$
が閉形式で表せるか、ということにあります。
　ここで注目したいこととして第二回の記事 (問題4)にて紹介したように
$\sum_{k = 0}^{n_{0}} (\binom{n}{k})$
という和は $n_{0}$ を用いた閉形式に表せないのに対し
$\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$
という和は $n$ についての閉形式に表せるという現象があります。
　このように二重数列の総和を考える上で興味深いのは"不定和分"ではなく"定和分"を求めることにあります(そもそも前者については Gosper's algorithm によって解決できます)。したがって以下では
$f (n) = \sum_{k = - \infty}^{\infty} F (n, k)$
という和の持つ性質について考えていきましょう。

和の範囲について

　ちなみに $F (n, k)$ が分母に $Γ (a n + b k)$ のような因子を持つときは $k = - \frac{a}{b} n$ を境にその前か後ろで $F (n, k)$ は常に $0$ となるので、いま考えている和は多くの場合ある有理数 $p, q$ を用いて
$f (n) = \sum_{p n \leq k \leq q n} F (n, k)$
や
$f (n) = \sum_{p n \leq k} F (n, k)$
のように表せます(無限和の場合は収束級数を考えるものとします)。
　また各 $n$ に対し $F (n, k)$ は $k$ についてill-definedな点を持つ場合もありますが、少なくともこのような範囲 $p n \leq k \leq q n$ においてwell-definedであれば気にしないものとします。

基本定理

　この問題において重要なのは、驚くべきことに、 $f (n)$ はP-再帰的であるという事実が成り立つことにあります。

　properな超幾何数列 $F (n, k)$ に対し $f (n) = \sum_{k} F (n, k)$ とおくと、ある(どれか一つは $0$ でない)多項式 $A_{i} (n)$ が存在して
$\sum_{i = 0}^{I} A_{i} (n) f (n + i) = 0$
が成り立つ。

　定理1により $F (n, k)$ は $k$ に依らない漸化式
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) F (n + i, k + j) = 0$
を満たすので、この左辺を $k$ について足し合わせることで
$\sum_{i = 0}^{I} (\sum_{j = 0}^{J} a_{i, j} (n)) f (n + i) = 0$
という漸化式を得る。

　 $f (n)$ がP-再帰的であるということはその閉形式を考えることができるということになります。
　また $f (n)$ の漸化式が得られればその閉形式は第一回の記事にて説明したようなステップによって求めることができるので、以下ではその「 $f (n)$ の満たす漸化式をどうやって求めるのか」という問題について考えていくこととしましょう。

Sister Celine's Algorithm

　素朴には上で説明したように定理1のような漸化式
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) F (n + i, k + j) = 0$
を求め、これを $k$ について足し合わせることで
$\sum_{i = 0}^{I} (\sum_{j = 0}^{J} a_{i, j} (n)) f (n + i) = 0$
という漸化式を得るという方法があります。
　また定理1のような漸化式はその導出をそのまま辿る、つまり以下のようなステップによって求めることができます。

$I, J$ を任意に取り、未知数 $a_{i, j} (n)$ についての方程式
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) F (n + i, k + j) = 0$
を考える。
各 $i, j$ に対し
$\frac{F (n + i, k + j)}{F (n, k)} = \frac{ν_{i, j} (n, k)}{δ_{i, j} (n, k)}$
なる多項式 $ν_{i, j} (n, k), δ_{i, j} (n, k)$ を求める。
$δ_{i, j} (n)$ の公倍多項式 $Δ (n, k)$ を求め
$\sum_{i = 0}^{I} \sum_{j = 0}^{J} a_{i, j} (n) ν_{i, j} (n, k) \frac{Δ (n, k)}{δ_{i, j} (n, k)} = 0$
という多項式の恒等式に帰着させる。
この両辺を $k$ について係数比較することによって得られる $a_{i, j} (n)$ についての線型方程式を解く。
もしその方程式が非自明な解を持たなければ $I, J$ をより大きく取り直して同様の試行を繰り返す。

Zeilberger's Algorithm

　しかし我々が求めたいのは
$A_{i} (n) = \sum_{j = 0}^{J} a_{i, j} (n)$
という多項式であり、この個々の $a_{i, j} (n)$ まで求める必要はありません。そこで $a_{i, j} (n)$ を経由せず直接 $A_{i} (n)$ を求めるために定理2のような漸化式
$\sum_{i = 0}^{I} A_{i} (n) F (n + i, k) = G (n, k + 1) - G (n, k)$
を考えてみましょう。
　なおある有理関数 $R (n, k)$ が存在して $G (n, k) = R (n, k) F (n, k)$ と書けるとのことだったので、適当な $k$ に対して $F (n, k) = 0$ なり $F (n, k) \to 0$ なりが成り立てば $G (n, k)$ にも同様の事実が成り立ち、したがって上の漸化式を $k$ について足し合わせることで
$\sum_{i = 0}^{I} A_{i} (n) f (n + i) = 0$
という $f (n)$ についての漸化式が得られることとなります。

問題の帰着

　いま考えている等式の左辺
$A (k) = \sum_{i = 0}^{I} A_{i} (n) F (n + i, k)$
を $k$ についての超幾何数列とみなすと
$A (k) = G (n, k + 1) - G (n, k)$
より $A (k)$ はGosper総和可能ということになります。したがってこの問題には Gosper's algorithm の考え方が応用できることになります。

ステップ1

　まず
$\frac{A (k + 1)}{A (k)} = \frac{a (k)}{b (k)} \frac{c (k + 1)}{c (k)}$
なる多項式 $a (k), b (k), c (k)$ を構成してみましょう。
　いま
$\frac{F (n + 1, k)}{F (n, k)} = \frac{r_{1} (n, k)}{s_{1} (n, k)}, \frac{F (n, k + 1)}{F (n, k)} = \frac{r_{2} (n, k)}{s_{2} (n, k)}$
とおくと
$\begin{aligned} \frac{A (k + 1)}{A (k)} & = \frac{\sum_{i = 0}^{I} A_{i} (n) \frac{F (n + i, k + 1)}{F (n, k + 1)}}{\sum_{i = 0}^{I} A_{i} (n) \frac{F (n + i, k)}{F (n, k)}} \frac{F (n, k + 1)}{F (n, k)} \\ = \frac{\sum_{i = 0}^{I} A_{i} (n) \prod_{j = 0}^{i - 1} \frac{r_{1} (n + j, k + 1)}{s_{1} (n + j, k + 1)}}{\sum_{i = 0}^{I} A_{i} (n) \prod_{j = 0}^{i - 1} \frac{r_{1} (n + j, k)}{s_{1} (n + j, k)}} \frac{r_{2} (n, k)}{s_{2} (n, k)} \\ = \frac{c_{0} (k + 1)}{c_{0} (k)} \frac{a_{0} (k)}{b_{0} (k)} \end{aligned}$
ただし
$\begin{aligned} a_{0} (k) & = r_{2} (n, k) \prod_{j = 0}^{I - 1} s_{1} (n + j, k) \\ b_{0} (k) & = s_{2} (n, k) \prod_{j = 0}^{I - 1} s_{1} (n + j, k + 1) \\ c_{0} (k) & = \sum_{i = 0}^{I} A_{i} (n) (\prod_{j = 0}^{i - 1} r_{1} (n + j, k) \prod_{j = i}^{I - 1} s_{1} (n + j, k)) \end{aligned}$
と表せます(ここで $a_{0} (k), b_{0} (k)$ は $A_{i} (n)$ の取り方に依らず定まる多項式であることに注意しましょう)。
　また Gosper's algorithm のステップ1によって
$\frac{a_{0} (k)}{b_{0} (k)} = \frac{a (k)}{b (k)} \frac{c_{1} (k + 1)}{c_{1} (k)}$
なる多項式 $a (k), b (k), c_{1} (k)$ であって任意の非負整数 $h$ に対し
$gcd (a (k), b (k + h)) = 1$
を満たすようなものを取り、 $c (k) = c_{0} (k) c_{1} (k)$ とおくと
$\frac{A (k + 1)}{A (k)} = \frac{a (k)}{b (k)} \frac{c (k + 1)}{c (k)}$
と表せることとなります。

ステップ2

　このとき
$G (n, k) = \frac{b (k - 1)}{c (k)} x (k) A (k)$
とおくと $x (k)$ は多項式であり
$a (k) x (k + 1) - b (k - 1) x (k) = c (k)$
を満たすのでした。
　ここで $a (k), b (k - 1)$ は $A_{i} (n)$ の取り方に依らず定まる多項式であったことに注意すると Gosper's algorithm のステップ2によって $x (n)$ の次数の上界 $d$ を求めることができます。このとき
$x (n) = \sum_{j = 0}^{d} B_{j} (n) k^{j}$
とおくと方程式
$a (k) x (k + 1) - b (k - 1) x (k) = c (k)$
は $k$ についての係数比較により $I + d + 2$ の未知数
$A_{0} (n), \dots, A_{I} (n), B_{0} (n), \dots, B_{d} (n)$
についての線型方程式に帰着でき、あとはこれを解くことで万事解決となります。

まとめ

　以上の議論をまとめると
$\sum_{i = 0}^{I} A_{i} (n) F (n + i, k) = G (n, k + 1) - G (n, k)$
を満たすような多項式 $A_{i} (n)$ および超幾何数列 $G (n, k)$ は以下のようなステップによって求めることができます。

$I$ を任意に取り、未知数 $A_{i} (n)$ および未知の超幾何数列 $G (n, k)$ についての方程式
$\sum_{i = 0}^{I} A_{i} (n) F (n + i, k) = G (n, k + 1) - G (n, k)$
を考える。
多項式 $r_{1}, r_{2}, s_{1}, s_{2}$ を
$\frac{F (n + 1, k)}{F (n, k)} = \frac{r_{1} (n, k)}{s_{1} (n, k)}, \frac{F (n, k + 1)}{F (n, k)} = \frac{r_{2} (n, k)}{s_{2} (n, k)}$
によって定め
$\begin{aligned} a_{0} (k) & = r_{2} (n, k) \prod_{j = 0}^{I - 1} s_{1} (n + j, k) \\ b_{0} (k) & = s_{2} (n, k) \prod_{j = 0}^{I - 1} s_{1} (n + j, k + 1) \\ c_{0} (k) & = \sum_{i = 0}^{I} A_{i} (n) (\prod_{j = 0}^{i - 1} r_{1} (n + j, k) \prod_{j = i}^{I - 1} s_{1} (n + j, k)) \end{aligned}$
とおく。
Gosper's algorithm のステップ1によって
$\frac{a_{0} (k)}{b_{0} (k)} = \frac{a (k)}{b (k)} \frac{c_{1} (k + 1)}{c_{1} (k)}$
なる多項式 $a (k), b (k), c_{1} (k)$ であって任意の非負整数 $h$ に対し
$gcd (a (k), b (k + h)) = 1$
を満たすようなものを取り、 $c (k) = c_{0} (k) c_{1} (k)$ とおく。
Gosper's algorithm のステップ2によって
$a (k) x (k + 1) - b (k - 1) x (k) = c (k)$
を満たすような多項式 $x (k)$ の次数の上界 $d$ を求め
$x (k) = \sum_{j = 0}^{d} B_{j} (n) k^{j}$
と展開し、 $k$ についての係数比較によって得られる
$A_{0} (n), \dots, A_{I} (n), B_{0} (n), \dots, B_{d} (n)$
についての線形方程式を解く。
もし非自明な解が得られれば
$\begin{aligned} G (n, k) & = \frac{b (k - 1)}{c (k)} x (k) \sum_{i = 0}^{I} A_{i} (n) F (n + i, k) \\ = \frac{b (k - 1)}{c_{1} (k) \prod_{j = 0}^{I - 1} s_{1} (n + j, k)} x (k) F (n, k) \end{aligned}$
が求める超幾何数列となる。
もし非自明な解が得られなければ $I$ をより大きく取り直して同様の試行を繰り返す。

計算例

　以下で簡単な計算例について紹介しておきますが、流石に二重数列の計算ともなると手計算が地獄となるので基本的には機械計算に頼った方がいいと思います。

$\sum_{k = 0}^{n} (\binom{n}{k}) x^{k} = (1 + x)^{n}$
を示せ。

解説

$F (n, k) = (\binom{n}{k}) x^{k}, f (n) = \sum_{k} F (n, k) = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k}$
とおく。これは二項係数の漸化式
$(\binom{n + 1}{k}) = (\binom{n}{k}) + (\binom{n}{k - 1})$
の両辺に $x^{k}$ を掛けることで
$F (n + 1, k) = F (n, k) + F (n, k - 1) x$
という漸化式を満たすことがわかる。
　したがってこれを $k$ について足し合わせることで
$f (n + 1) = (1 + x) f (n)$
という漸化式が得られ、また $f (0) = 1$ に注意すると
$f (n) = (1 + x)^{n}$
と求まる。

$\sum_{n = k}^{\infty} (\binom{n}{k}) y^{n} = \frac{y^{k}}{(1 - y)^{k + 1}}$
を示せ。

解説

$F (n, k) = (\binom{n}{k}) y^{n}, g (k) = \sum_{n} F (n, k) = \sum_{n = k}^{\infty} (\binom{n}{k}) y^{n}$
とおくと、これも二項係数の漸化式から
$F (n + 1, k) = F (n, k) y + F (n, k - 1) y$
という漸化式を満たすことがわかる。
　したがってこれを $n$ について足し合わせることで
$g (k) = g (k) y + g (k - 1) y$
つまり
$g (k) = \frac{y}{1 - y} g (k - 1)$
という漸化式が得られ、また
$g (0) = \sum_{n = 0}^{\infty} y^{n} = \frac{1}{1 - y}$
に注意すると
$g (k) = \frac{y^{k}}{(1 - y)^{k + 1}}$
と求まる。

$\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n})$
を示せ。

解説

$F (n, k) = {(\binom{n}{k})}^{2}, f (n) = \sum_{k = 0}^{n} {(\binom{n}{k})}^{2}$
とおきZeilberger's algorithmを実行する。
　とりあえず $I = 1$ とし
$A (k) = A_{0} (n) {(\binom{n}{k})}^{2} + A_{1} (n) {(\binom{n + 1}{k})}^{2}$
とおく。このとき
$\begin{aligned} \frac{A (k + 1)}{A (k)} & = \frac{A_{0} (n) {(\frac{n - k}{k + 1})}^{2} + A_{1} (n) {(\frac{n + 1}{k + 1})}^{2}}{A_{0} (n) + A_{1} (n) {(\frac{n + 1}{n + 1 - k})}^{2}} \\ = \frac{A_{0} (n) (n - k)^{2} + A_{1} (n) (n + 1)^{2}}{A_{0} (n) (n + 1 - k)^{2} + A_{1} (n) (n + 1)^{2}} {(\frac{n + 1 - k}{k + 1})}^{2} \end{aligned}$
が成り立つので
$a (k) = (n + 1 - k)^{2}, b (k) = (k + 1)^{2}, c (k) = A_{0} (n) (n + 1 - k)^{2} + A_{1} (n) (n + 1)^{2}$
とおくとよい。
　このとき
$(n + 1 - k)^{2} x (k + 1) - k^{2} x (k) = A_{0} (n) (n + 1 - k)^{2} + A_{1} (n) (n + 1)^{2}$
なる多項式 $x (n)$ が存在すればその次数は高々 $1$ であることがわかるので
$x (n) = B_{0} (n) + B_{1} (n) k$
とおくと $k$ についての係数比較によって
$\begin{aligned} (B_{0} + B_{1}) - 2 (n + 1) B_{1} - B_{0} & = A_{0} \\ - 2 (n + 1) (B_{0} + B_{1}) + (n + 1)^{2} B_{1} & = - 2 (n + 1) A_{0} \\ (n + 1)^{2} (B_{0} + B_{1}) & = (n + 1)^{2} (A_{0} + A_{1}) \end{aligned}$
つまり
$(\begin{matrix} 1 & 0 & 0 & 2 n + 1 \\ 2 & 0 & - 2 & n - 1 \\ 1 & 1 & - 1 & - 1 \end{matrix}) (\begin{matrix} A_{0} \\ A_{1} \\ B_{0} \\ B_{1} \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix})$
という方程式が得られるので、これを解くことでその解の一つとして
$A_{0} = - 2 (2 n + 1), A_{1} = n + 1, B_{0} = - 3 (n + 1), B_{1} = 2$
と求まる。
　以上より
$A_{1} (n) f (n + 1) + A_{0} (n) f (n) = (n + 1) f (n + 1) - 2 (2 n + 1) f (n) = 0$
という漸化式が得られ、また $f (0) = 1$ に注意すると
$f (n) = \frac{2 n (2 n - 1)}{n^{2}} f (n - 1) = \frac{(2 n)!}{(n!)^{2}} f (0) = (\binom{2 n}{n})$
と求まる。
　ちなみにこのとき
$x (k) = B_{1} k + B_{0} = 2 k - 3 n - 3$
であったのでこれによって $G (n, k)$ は
$G (n, k) = \frac{k^{2} (2 k - 3 n - 3)}{(n - k + 1)^{2}} F (n, k)$
と求まる。またこの問題をSister Celine's algorithmによって解く場合は
$\begin{aligned} n F (n, k) & - (2 n - 1) (F (n - 1, k) + F (n - 1, k - 1)) \\ + (n - 1) (F (n - 2, k) - 2 F (n - 2, k - 1) + F (n - 2, k - 2)) = 0 \end{aligned}$
という漸化式が得られる。