Loading article…
数学 において、ビル・ゴスパーによるゴスパーのアルゴリズムは、それ自体が超幾何項である超幾何項の和を求める手順です。つまり、a (1) + ... + a ( n ) = S ( n ) − S (0) があるとします。ここで、S ( n ) は超幾何項です (つまり、S ( n + 1)/ S ( n ) はnの有理関数です)。すると、必然的にa ( n ) 自体が超幾何項となり、 a ( n )の式が与えられれば、ゴスパーのアルゴリズムはS ( n )についてそれを見つけます。
ステップ 1: b ( n ) = a ( n )/ p ( n )と書くと、比b ( n )/ b ( n − 1 ) がq ( n )/ r ( n )の形になるような多項式p を見つけます。ここで、qとr は多項式であり、どのq ( n ) もr ( n + j ) ( j = 0, 1, 2, ... )と非自明な因数を持ちません。（これは、級数が閉じた形で総和可能かどうかに関わらず、常に可能です。）
ステップ 2: S ( n ) = q ( n + 1)/ p ( n ) ƒ ( n ) a ( n )となるような多項式ƒを見つけます。級数が閉じた形で総和可能であれば、この性質を持つ有理関数ƒが存在することは明らかです。実際、それは常に多項式でなければならず、その次数の上限を見つけることができます。ƒ を決定する (またはそのようなƒ が存在しないことを発見する) ことは、連立一次方程式を解くことの問題です。[ 1 ]
ゴスパーのアルゴリズムは、存在する場合にウィルフ・ツァイルベルガーのペアを発見するために使用できます。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 の関数である k の関数として扱います。この設定では、アルゴリズムのすべての機能が動作します。）S ( k ) がS ( k ) − S ( k − 1) = a ( 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コンピュータ代数システムの開発に取り組んでいた際に、このアルゴリズムを発見した。
アルゴリズム／二項係数恒等式／閉形式／記号計算／線形漸化式