超幾何数列の基礎3：漸化式の解き方

はじめに

　この記事では 前回の記事 に引き続き超幾何数列の基本事項についてまとめていきます。
　前回の記事では
$$S(n)=\sum^n_{k=0}A(k)$$
という数列の閉形式の求め方、特に
$$T(n+1)-T(n)=A(n)$$
という漸化式を満たす超幾何数列の求め方について解説しましたが、今回の記事ではより一般に多項式係数の線形漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=0$$
を満たす超幾何数列の求め方について解説していきます。
　以下$p_0(n),\ldots,p_I(n)$は多項式であって、$p_0(n),p_I(n)$は(多項式として)$0$ではないものとします。

多項式による解

　まず非同次な漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=g(n)$$
の多項式による解の求め方について考えていきましょう。$f(n)$が多項式であればこの左辺も多項式となるので、以下この右辺$g(n)$は多項式であるものとします。
　やることとしては適当に$d$を取り
$$f(n)=\sum^d_{k=0}c_kn^k$$
と展開することによって$d+1$個の未知数$c_0,\ldots,c_d$についての線型方程式に帰着させるだけなので、あとは$d$の上界を求めておけば機械的に処理することができます。

漸化式から差分方程式へ

　いま簡単のため$N$を前進作用素、つまり数列$a_n$に対して
$$Na_n=a_{n+1}$$
と定めると件の方程式は
$$L=\sum^I_{i=0}p_i(n)N^i$$
なる作用素を用いて
$$Lf(n)=g(n)$$
と表せます。
　また$\D$を差分作用素、つまり数列$a_n$に対して
$$\D a_n=a_{n+1}-a_n$$
と定めると$\D=N-1$より$L$は$\D$を用いて
\begin{align} L &=\sum^I_{i=0}p_i(n)(\D+1)^i\\ &=\sum^I_{i=0}p_i(n)\sum^i_{j=0}\binom ij\D^j\\ &=\sum^I_{j=0}\l(\sum^I_{i=j}\binom ijp_i(n)\r)\D^j \end{align}
と表せます。
　したがって件の方程式は
$$q_j(n)=\sum^I_{i=j}\binom ijp_i(n)$$
なる多項式を係数に持つ差分方程式
$$\sum^I_{j=0}q_j(n)(\D^jf)(n)=g(n)$$
に変形できます。

次数の推定

　いま$f(n)$の次数を$d$とおき
$$f(n)=cn^d+\cdots$$
と展開すると、繰り返しこの差分を取ることで
$$(\D^jf(n))=cd^{\ul j}n^{d-j}+\cdots$$
が成り立ちます。ただし$x^{\ul j}$は下降階乗
$$x^{\ul j}=x(x-1)(x-2)\cdots(x-j+1)$$
としました。
　したがって
$$q_j(n)=\la_jn^{d_j}+\cdots\qquad(d_j=\deg q_j)$$
および
$$b=\max_{0\leq j\leq I}(\deg q_j-j)$$
とおくと
$$Lf(n)=\sum^I_{j=0}q_j(n)(\D^jf)(n)$$
の次数は高々$b+d$であり、また$n^{b+d}$の係数は
$$c\sum_{\deg q_j-j=b}\la_jd^{\ul j}$$
と表せます。
　これによって$d$は次のいずれかの条件を満たすことがわかります。

• $b+d<0$のとき、$d\leq-b-1$
• $\deg(Lf(n))=b+d$のとき、$d=\deg g-b$
• $\deg(Lf(n))< b+d$のとき、多項式
  $$r(x)=\sum_{\deg q_j-j=b}\la_jx^{\ul j}$$
  に対し$r(d)=0$

まとめ

　以上より漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=g(n)$$
の多項式解は次のようなアルゴリズムによって網羅的に求めることができます。

　ちなみに 前回の記事 Gosper's algorithmのステップ2として
$$a(n)x(n+1)-b(n-1)x(n)=c(n)$$
という漸化式の多項式解$x(n)$の求め方を紹介しましたが、それはこのアルゴリズムの特殊な例($I=1$)となっています。

超幾何数列による解

　次に上の結果を用いて同次漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=0$$
の超幾何数列による解の求め方について考えていきましょう。
　いま超幾何数列$f(n)$に対し
$$r(n)=\frac{f(n+1)}{f(n)}$$
とおくと$f(n)$は
$$f(n)=f(0)\prod^{n-1}_{k=0}r(n)$$
のように表せるので、件の方程式は有理関数$r(n)$についての方程式
\begin{align} &\sum^I_{i=0}p_i(n)\frac{f(n+i)}{f(n)}\\ ={}&\sum^I_{i=0}p_i(n)\prod^{i-1}_{j=0}r(n+j)=0 \end{align}
に帰着できます。

$r(n)$の因数

　ここで 前回の記事 の定理5から
$$r(n)=\frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}z$$
なるモニック多項式$a(n),b(n),c(n)$と定数$z$であって

1. 任意の非負整数$h$に対し$a(n)$と$b(n+h)$は互いに素である。
2. $a(n)$と$c(n)$は互いに素である。
3. $b(n)$と$c(n+1)$は互いに素である。

を満たすようなものを取ると
$$\prod^{i-1}_{j=0}r(n+j)=\l(\prod^{i-1}_{j=0}\frac{a(n+j)}{b(n+j)}\r)\frac{c(n+i)}{c(n)}z^i$$
が成り立つので件の方程式はさらに多項式の恒等式
$$\sum^I_{i=0}p_i(n)\l(\prod^{i-1}_{j=0}a(n+j)\prod^{I-1}_{j=i}b(n+j)\r)c(n+i)z^i=0$$
に帰着されます。
　いまこの左辺の第$i=0,I$項に注目すると
\begin{align} a(n)&\mid p_0(n)\l(\prod^{I-1}_{j=0}b(n+j)\r)c(n)\\ b(n+I-1)&\mid p_I(n)\l(\prod^{I-1}_{j=0}a(n+j)\r)c(n+I)z^I \end{align}
が成り立つことがわかり、特に$a(n),b(n),c(n)$の取り方から
$$a(n)\mid p_0(n),\quad b(n)\mid p_I(n-I+1)$$
となることがわかります。これにより$a(n),b(n)$の候補は$p_0(n),p_i(n-I+1)$の因数という高々有限個に絞ることができます。

多項式解への帰着

　そこで$p_0(n),p_i(n-I+1)$のモニックな因数を任意に取って$a(n),b(n)$とおき、件の方程式
$$\sum^I_{i=0}p_i(n)\l(\prod^{i-1}_{j=0}a(n+j)\prod^{I-1}_{j=i}b(n+j)\r)c(n+i)z^i=0$$
を$c(n),z$についての方程式として解いてみましょう。
　このときこの最高次の係数に注目することで$z$についての代数方程式(明示形については後述)
$$\sum^I_{i=0}\a_iz^i=0$$
が得られるので、この代数方程式の解$z_0$を任意に取り$z=z_0$とすることで残すは線形漸化式の多項式解$c(n)$を求めるだけとなります。そしてそれは前節で紹介したアルゴリズムによって解決することができます。

Petkivšek's Algorithm

　以上より漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=g(n)$$
の超幾何数列による解は次のようなアルゴリズムによって網羅的に求めることができます。

　見ての通りこのアルゴリズムは計算量が半端ではありません。実際"A=B"によると最悪の場合この計算量は$p_0(n),p_I(n)$の次数に関して指数的なオーダーとなるらしいです。そのため少しでも計算量を減らす工夫として以下のテクニックを覚えておくといいでしょう。

計算例

　百聞は一見に如かず、ということで今回も"A=B"に掲載されているいくつかの計算例を見ていくこととしましょう。

　やはり計算量が大変なことになってしまうので、やむを得ず多項式解を計算する過程は省略しました。

追記：d'Alembertian数列による解

　上では漸化式の超幾何数列による解の求め方について解説してきましたが、"閉じた形(closed form)"の解釈をもう少し広げ
$$f(n) =A_0(n)\sum^{n-1}_{n_1=0}A_1(n_1)\sum^{n_1-1}_{n_n=0}A_2(n_2)\cdots\sum^{n_{d-1}-1}_{n_d=0}A_d(n_d)$$
と表せるような解について考えてみましょう。

　例えば超幾何数列$A_0(n),A_1(n)$を用いて
$$f(n)=A_0(n)\sum^n_{k=0}A_1(k)$$
と表せるような数列は
$$\l(N-\frac{A_0(n+2)A_1(n+2)}{A_0(n+1)A_1(n+1)}\r)\l(N-\frac{A_0(n+1)}{A_0(n)}\r)f(n)=0$$
という漸化式を満たします。
　ここでこの漸化式は$f(n)=A_0(n)$も解に持つことに注意しましょう。

漸化式の階数下げ

　いま与えられた漸化式のd'Alembertian数列による解を考える上で重要な事実として次のような命題が成り立ちます(証明については気が向いたら書きます)。

　このような$A(n)$に対して
$$g(n)=\frac{f(n)}{A(n)},\quad h(n)=g(n+1)-g(n)$$
とおくとこの漸化式の階数を下げることができます。実際これにより
\begin{align} &\phantom{={}}\sum^I_{i=0}p_i(n)f(n+i)\\ &=p_I(n)A(n+I)g(n+I)+\sum^{I-1}_{i=0}p_i(n)A(n+i)g(n+i)\\ &=\l(-\sum^{I-1}_{i=0}p_i(n)A(n+i)\r)g(n+I)+\sum^{I-1}_{i=0}p_i(n)A(n+i)g(n+i)\\ &=\sum^{I-1}_{i=0}p_i(n)A(n+i)(g(n+i)-g(n+I))\\ &=\sum^{I-1}_{i=0}p_i(n)A(n+i)\sum^{I-1}_{j=i}(g(n+j)-g(n+j+1))\\ &=\sum^{I-1}_{j=0}\l(\sum^j_{i=0}p_i(n)A(n+i)\r)(g(n+j)-g(n+j+1))\\ \end{align}
と変形できるので$h(n)$は$I-1$階の漸化式
$$\sum^{I-1}_{j=0}\l(\sum^j_{i=0}p_i(n)\frac{A(n+i)}{A(n)}\r)h(n+j)=0$$
を満たすことがわかります。
　また$f(n)$がd'Alembertianであれば$h(n)$も再びd'Alembertianとなるのでこれが$0$でなければ$h(n)$についての漸化式にも超幾何数列による解$A'(n)$が存在することになります。このようにして超幾何数列による解が求まらなくなるまで階数を下げていくことで
\begin{align} f(n)={} &A(n),\\ &A(n)\sum^{n-1}_{n_1=0}A'(n_1),\\ &A(n)\sum^{n-1}_{n_1=0}A'(n_1)\sum^{n_1-1}_{n_2=0}A''(n_2),\\ &\quad\vdots \end{align}
といった形の解が得られることとなります。

計算例

　やはりこれも百聞は一見に如かず、ということで計算例をいくつか紹介しておきましょう。

　ちなみにこの階数下げのテクニックは単に超幾何数列による解を求める場合にも役に立ちます。

　このようにd'Alembertian数列による解
$$f(n)=A(n)\sum^n_{k=0}A'(k)$$
が得られても、$A'(n)$がGosper総和可能であれば
$$T(n+1)-T(n)=A'(k)$$
なる超幾何数列$T(n)$を用いて
$$f(n)=A(n)T(n+1)-A(n)T(0)$$
という閉形式が得られることにも注意しなければなりません。
　ちなみに問題4の場合は
$$A'(n)=\frac{(-1)^n}{n!}$$
がGosper総和可能ではないのであれが最善の結果となっています。

追記：三項間漸化式の一般解

　よくよく考えると三項間漸化式は解が一つ求まれば次のような解の公式を作れることに気付いたので簡単に書いておきます。

　例えばこれにより上の問題1の一般解も簡単に求めることができます。