P再帰方程式

1980年代後半、セルゲイ・A・アブラモフは、漸化式の一般多項式解を求めるアルゴリズムを記述した。${\textstyle y(n)\in \mathbb {K} [n]}$右辺が多項式である${\textstyle f(n)\in \mathbb {K} [n]}$彼（そして数年後、マルコ・ペトコフシェク）は多項式解の次数上限を与えた。この方法では、線形方程式系を考えることで簡単に問題を解くことができる。^{[ 2 ] [ 3 ] [ 4 ]} 1995年、アブラモフ、ブロンシュタイン、ペトコフシェクは、多項式の場合、特定の冪基底（つまり通常の基底ではない）での漸化式の冪級数解を考えることで、より効率的に解けることを示した。${\textstyle (x^{n})_{n\in \mathbb {N} }}$[ ^{5 ]​}

より一般的な解（例えば、有理数解や超幾何数解）を見つけるための他のアルゴリズムも、多項式解を計算するアルゴリズムに依存している。

1989年、セルゲイ・A・アブラモフは、一般的な合理的解、すなわち${\textstyle y(n)\in \mathbb {K} (n)}$右辺が多項式の場合${\textstyle f(n)\in \mathbb {K} [n]}$は、普遍分母の概念を用いることで求めることができる。普遍分母とは多項式である。${\textstyle u}$すべての有理解の分母が割り切れるように${\textstyle u}$アブラモフは、この普遍分母が最初の係数と最後の係数の多項式のみを使用して計算できることを示した。${\textstyle p_{0}}$そして${\textstyle p_{r}}$この普遍分母を未知の分母に代入すると、${\displaystyle y}$変換された方程式のすべての多項式解を計算することで、すべての有理解を見つけることができます。^{[ 6 ]}

シーケンス${\textstyle y(n)}$連続する 2 つの項の比が有理関数である場合、は超幾何関数と呼ばれます。${\displaystyle n}$つまり${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$これは、数列が多項式係数を持つ1階漸化式の解である場合に限ります。超幾何数列の集合は加法に関して閉じていないため、数列空間の部分空間ではありません。

1992年、マルコ・ペトコフシェクは、右辺が${\displaystyle f}$は超幾何数列の和です。このアルゴリズムは、有理関数のゴスパー・ペトコフシェク標準形を利用します。この特定の表現では、変換された方程式の多項式解を再び考慮するだけで十分です。^{[ 3 ]}

マーク・ファン・ホーイによる、より効率的な別のアプローチがある。最初の係数多項式と最後の係数多項式の根を考慮すると、${\textstyle p_{0}}$そして${\textstyle p_{r}}$特異点と呼ばれるものを利用して、超幾何数列は${\textstyle y(n)}$形式を表す$${\displaystyle y(n)=c\,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2}}\cdots \Gamma (n-\xi _{s})^{e_{s}}}$$一部の人にとって${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K} }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$と${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$のために${\textstyle i\neq j}$そして${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$。 ここ$\textstyle \Gamma (n)$はガンマ関数を表し、${\textstyle {\overline {\mathbb {K} }}}$体の代数的閉包${\textstyle \mathbb {K} }$それから${\textstyle \xi _{1},\dots ,\xi _{s}}$は方程式の特異点（つまり、${\textstyle p_{0}}$または${\textstyle p_{r}}$さらに、指数の上限を計算することもできます。${\textstyle e_{i}}$固定値の場合${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$候補を与える仮説を立てることが可能である。${\textstyle z}$特定の${\textstyle z}$有理関数を得るための仮説を再び立てることができる${\textstyle r(n)}$アブラモフのアルゴリズムにより、すべての可能性を考慮すると、漸化式の一般解が得られます。^{[ 7 ] [ 8 ]}

シーケンス${\displaystyle y}$ダランベール式と呼ばれるのは、$y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$いくつかの超幾何数列について${\textstyle h_{1},\dots ,h_{k}}$そして${\textstyle y=\sum x}$つまり${\textstyle \Delta y=x}$どこ${\textstyle \Delta }$は差分演算子を表します。${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$これは、一次線形漸化式演算子が存在する場合に限り成り立つ。${\textstyle L_{1},\dots ,L_{k}}$有理係数で、${\textstyle L_{k}\cdots L_{1}y=0}$[ ^{4 ]​}

1994年、アブラモフとペトコフシェクは、漸化式の一般ダランベール解を計算するアルゴリズムを記述した。このアルゴリズムは超幾何解を計算し、漸化式の次数を再帰的に下げる。^{[ 9 ]}

サイズが の符号付き順列行列の数${\displaystyle n\times n}$シーケンスで説明できます${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {N} }}$符号付き置換行列は、各行と各列にちょうど 1 つの非ゼロ要素を持つ正方行列です。非ゼロ要素は、${\textstyle \pm 1}$数列は、多項式係数を持つ線形漸化式によって決定される。$${\displaystyle y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)}$$そして初期値${\textstyle y(0)=1,y(1)=2}$超幾何解を求めるアルゴリズムを適用することで、一般超幾何解を求めることができる。$${\displaystyle y(n)=c\,2^{n}n!}$$ある定数に対して${\textstyle c}$また、初期値を考慮すると、数列は${\textstyle y(n)=2^{n}n!}$符号付き順列行列の数を表します。^{[ 10 ]}

内反の数${\textstyle y(n)}$セットの${\textstyle n}$要素は漸化式で与えられる$${\displaystyle y(n)=(n-1)\,y(n-2)+y(n-1).}$$例えばペトコフシェクのアルゴリズムを適用すると、この漸化式には多項式、有理数、超幾何式の解が存在しないことがわかる。^{[ 4 ]}