ゴスパーのアルゴリズム - 百科事典

数学において、ビル・ゴスパーに因むゴスパーのアルゴリズムは、自らも超幾何級数の和を求める超幾何級数の和を求める手順です。つまり、S(n)が超幾何級数であることを仮定して、a(1) + ... + a(n) = S(n) − S(0)であるとすると、a(n)自体も超幾何級数であることが必然的です。そして、a(n)の公式を与えられた場合、ゴスパーのアルゴリズムはS(n)に対してそれを見つけます。

アルゴリズムの概要
ステップ1：p(n)を持つ多項式pを求め、b(n) = a(n)/p(n)とすると、b(n)/b(n − 1)がq(n)/r(n)の形を持ち、qとrが多項式で、q(n)にr(n + j)（j = 0, 1, 2, ...）が非平凡な因子を持たないことを満たすような比を持つようにします（これは系列が閉形式で和可能であるかどうかに関係なく常に可能です）。
ステップ2：S(n) = q(n + 1)/p(n) ƒ(n) a(n)を持つ多項式ƒを求めます。系列が閉形式で和可能である場合、このような性質を持つ有理関数ƒが明らかに存在します；実際には常に多項式であり、その次数の上限が見つかるべきです。ƒの決定（またはそのようなƒがないことを見つける）は、線形方程式のシステムを解くことになります。

ウィルフ–ゼイルバーガープラールへの関係
ゴスパーのアルゴリズムは、ウィルフ–ゼイルバーガープラールを発見するために使用できます。F(n + 1, k) − F(n, k) = G(n, k + 1) − G(n, k)で、Fは既知であるがGは未知であると仮定します。それでは、a(k) := F(n + 1, k) − F(n, k)をゴスパーのアルゴリズムにフィードします（この設定では、係数がnの関数ではなく数の関数であると見做します；アルゴリズムのすべてがこの設定で動作します）。成功してS(k)を見つけた場合、これは必要なGです。それ以外の場合、そのようなGは存在しません。

定義的積分と無限積分
ゴスパーのアルゴリズムは（可能な場合は）超幾何級数の無限積分の超幾何級数の閉形式を見つけます。そのような閉形式が存在しない場合でも、全てのnの和または特定のnの値の集合の和が閉形式を持つことがあります。この問題は、係数が他の変数の関数である場合にのみ意味があります。したがって、a(n,k)がnとkの両方で超幾何級数であると仮定します：つまり、a(n, k)/a(n − 1,k)とa(n, k)/a(n, k − 1)がnとkの有理関数であるとします。それでは、ゼイルバーガーのアルゴリズムとペトコヴシェクのアルゴリズムを使用して、a(n, k)のkに対する和の閉形式を見つけることができます。

歴史
ビル・ゴスパーは1970年代にSAILとMITのMacsymaコンピュータ代数システムに取り組んでいる間に、このアルゴリズムを発見しました。

脚注


参考文献
Gosper, Jr., Ralph William "Bill" (January 1978) [1977-09-26]. "Decision procedure for indefinite hypergeometric summation" (PDF). Proceedings of the National Academy of Sciences of the United States of America. Mathematics. 75 (1). Xerox, Palo Alto Research Center, Palo Alto, California, USA: 40–42. Bibcode:1978PNAS...75...40G. doi:10.1073/pnas.75.1.40. PMC 411178. PMID 16592483. Archived (PDF) from the original on 2019-04-12. Retrieved 2020-01-10. algorithm / binomial coefficient identities / closed form / symbolic computation / linear recurrences