超幾何数列の基礎6：Markov-WZ method
はじめに
この記事では
前回の記事
に引き続き超幾何数列の基本事項についてまとめていきます。
前回の記事では
$$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$
を満たすような数列の組$F,G$を用いた級数の変形や求値に関する手法WZ methodについて解説しました。
しかし実用的には与えられた級数
$$\sum^\infty_{k=0}A(k)$$
に対してWZ methodを適用したいと思っても
$$F(0,k)=A(k)$$
を満たすようなWZ-pair$F,G$が見つからなければ話は始まりません。
今回の記事ではそんなときに適当なWZ-pairを構成するための手法Markov-WZ methodについて解説していきます。
Markov-WZ method
いま与えられた級数
$$\sum^\infty_{k=0}A(k)$$
に対しWZ methodを適用したいものとします。このときまず
$$H(0,k)=A(k)$$
なるproperな超幾何数列$H(n,k)$を任意に取り、$H(n,k)$に関するWZ-pairを構成することを考えましょう。
具体的にMarkov-WZ methodでは次のような問題を考えます。
与えられたproperな超幾何数列$H(n,k)$に対し、ある$k$についての($0$でない)多項式
$$P(n,k)=\sum^d_{j=0}A_j(n)k^j$$
およびある数列$G(n,k)$であって、$F(n,k)=P(n,k)H(n,k)$と$G(n,k)$がWZ-pairとなるようなものは存在するだろうか。また存在すればそれらはどのように求められるだろうか。
問題の帰着
さてこの問題は
$$P(n+1,k)H(n+1,k)-P(n,k)H(n,k)=G(n,k+1)-G(n,k)$$
なる$P,G$を構成することにありますが、この右辺
$$\A(k)=P(n+1,k)H(n+1,k)-P(n,k)H(n,k)$$
を$k$についての超幾何数列とみなすと
$$\A(k)=G(n,k+1)-G(n,k)$$
より$\A(k)$はGosper総和可能ということになります。したがってこの問題には
Gosper's algorithm
の考え方が応用できることになります。
MWZ Algorithm
こう言い換えてしまえばあとはやることとしては Zeilberger's algorithm と全く同じなので、詳細は省いて結果として得られるアルゴリズムだけを紹介しておきましょう。
- $d$を任意に取り、$k$に関する未知の$d$次多項式$P(n,k)$と未知の超幾何数列$G(n,k)$についての方程式
$$P(n+1,k)H(n+1,k)-P(n,k)H(n,k)=G(n,k+1)-G(n,k)$$
を考える。 - 多項式$r_1,r_2,s_1,s_2$を
$$\frac{H(n+1,k)}{H(n,k)}=\frac{r_1(n,k)}{s_1(n,k)},\quad \frac{H(n,k+1)}{H(n,k)}=\frac{r_2(n,k)}{s_2(n,k)}$$
によって定め
\begin{align} a_0(k)&=r_2(n,k)s_1(n,k)\\ b_0(k)&=s_2(n,k)s_1(n,k+1)\\ c_0(k)&=P(n+1,k)r_1(n,k)-P(n,k)s_1(n,k) \end{align}
とおく。 -
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(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'$を求め
$$P(n,k)=\sum^d_{j=0}A_j(n)k^j,\quad x(k)=\sum^{d'}_{j=0}B_j(n)k^j$$
と展開し、$k$についての係数比較によって得られる
$$A_0(n),\ldots,A_d(n),A_0(n+1),\ldots,A_d(n+1),B_0(n),\ldots,B_{d'}(n)$$
についての線型方程式を整理し
$$\begin{pmatrix} A_0(n+1)\\\vdots\\A_d(n+1) \end{pmatrix} =\R(n)\begin{pmatrix} A_0(n)\\\vdots\\A_d(n) \end{pmatrix},\quad\begin{pmatrix} B_0(n)\\\vdots\\B_{d'}(n+1) \end{pmatrix} =\S(n)\begin{pmatrix} A_0(n)\\\vdots\\A_d(n) \end{pmatrix}$$
のような形に帰着させる。 - もしこのように整理できればこれによって定まる
\begin{align} G(n,k) &=\frac{b(k-1)}{c(k)}x(k)(P(n+1,k)H(n+1,k)-P(n,k)H(n,k))\\ &=\frac{b(k-1)}{c_1(k)s_1(n,k)}x(k)H(n,k) \end{align}
が求める超幾何数列となる。
もしステップ4が失敗すれば$d$をより大きく取り直してステップ4を繰り返す($a(k),b(k)$は$d$の取り方に依らないことに注意する)。
ちなみにこのステップ3において
$$\frac{a_0(k)}{b_0(k)}=\frac{a(k)}{b(k)}$$
とできる場合は
$$G(n,k)=s_2(n,k-1)x(k)H(n,k)$$
と求められます。
解の存在性について
ステップ4において得られる線型方程式の未知数の個数は$2(d+1)+(d'+1)$であり方程式の本数は$\deg c+1$本なので、$\deg c,d'$はそれぞれ$d$に比例することに注意すると十分大きい$d$に対し
$$(\mbox{未知数の個数})-(\mbox{方程式の本数})>0$$
となってそれは非自明な解を持つことがわかります($A_j(n)$と$A_j(n+1)$の値が整合するかはわかりませんが)。
計算例
物は試しということでまあ何か計算してみましょう。
$$H(n,k)=\l(\frac{n!k!}{(n+k)!}\r)^4$$
に関するWZ-pairを構成せよ。
解説
$$\A(k)=P(n+1,k)\l(\frac{(n+1)!k!}{(n+k+1)!}\r)^4-P(n,k)\l(\frac{n!k!}{(n+k)!}\r)^4$$
とおくと
$$\frac{\A(k+1)}{\A(k)}
=\frac{P(n+1,k+1)(n+1)^4-P(n,k+1)(n+k+2)^4}{P(n+1,k)(n+1)^4-P(n,k)(n+k+1)^4}\frac{(k+1)^4}{(n+k+2)^4}$$
が成り立つので
\begin{align}
a(k)&=(k+1)^4\\
b(k)&=(n+k+2)^4\\
c(k)&=P(n+1,k)(n+1)^4-P(n,k)(n+k+1)^4
\end{align}
とおくとよい。
このとき多項式$x(k)$に関する方程式
$$(k+1)^4x(k+1)-(n+k+1)^4x(k)=(n+1)^4P(n+1,k)-(n+k+1)^4P(n,k)$$
を考えると左辺の次数は$d'+3$、右辺の次数は$d+4$と推定できるので$d'+3=d+4$および
$$(2d+d'+3)-(d+5)=d+d'-2\geq1$$
となるように$d=1,d'=2$とし
$$P(n,k-1)=A_0(n)+A_1(n)k,\quad x(k-1)=B_0(n)+B_1(n)k+B_2(n)k^2$$
とおいてみる。
すると係数比較により
\begin{align}
B_1+4nB_2-(B_1+2B_2)&=A_1(n)\\
B_0+4nB_1+6n^2B_2-(B_0+B_1+B_2)&=A_0(n)+4nA_1(n)\\
4nB_0+6n^2B_1+4n^3B_2&=4nA_0(n)+6n^2A_1(n)\\
6n^2B_0+4n^3B_1+n^4B_2&=6n^2A_0(n)+4n^3A_1(n)\\
4n^3B_0+n^4B_1&=4n^3A_0(n)+n^4A_1(n)-(n+1)^4A_1(n+1)\\
n^4B_0&=n^4A_0(n)-(n+1)^4A_0(n+1)
\end{align}
つまり
\begin{align}
\begin{pmatrix}
0&0&2(2n-1)&0&0\\
0&4n-1&6n^2-1&0&0\\
2&3n&2n^2&0&0\\
6&4n&n^2&0&0\\
4n^3&n^4&0&0&(n+1)^4\\
n^4&0&0&(n+1)^4&0
\end{pmatrix}\begin{pmatrix}
B_0\\B_1\\B_2\\A_0(n+1)\\A_1(n+1)
\end{pmatrix}=\begin{pmatrix}
0&1\\1&4n\\2&3n\\6&4n\\4n^3&n^4\\n^4&0
\end{pmatrix}\begin{pmatrix}
A_0(n)\\A_1(n)
\end{pmatrix}
\end{align}
という方程式が得られる。これを適当に変形していくことで
\begin{align}
A_0(n)&=\frac{n-1}2A_1(n)\\
B_2&=\frac1{2(2n-1)}A_1(n)\\
B_1&=\frac{3n-2}{2(2n-1)}A_1(n)\\
B_0&=\frac{5n^2-6n+2}{4(2n-1)}A_1(n)\\
A_1(n+1)&=-\frac{n^5}{2(2n-1)(n+1)^4}A_1(n)
\end{align}
が得られるので$A_1(1)=1$つまり
$$A_1(n+1)=(-1)^n\frac{(n!)^2}{(n+1)^4(2n)!}$$
とおくとこれによって
\begin{align}
\ol H(n,k)
&=A_1(n+1)H(n+1,k)\\
&=(-1)^n\frac{(n!)^2}{(2n)!}\l(\frac{n!k!}{(n+k+1)!}\r)^4\\
F(n,k)&=\frac{n+2(k+1)}2\ol H(n,k)\\
G(n,k)
&=\frac{(5n^2+4n+1)+2(3n+1)(k+1)+2(k+1)^2}{4(2n+1)}\ol H(n,k)\\
&=\frac{5(n+1)^2+6(n+1)k+2k^2}{4(2n+1)}\ol H(n,k)\\
\end{align}
というWZ-pairが求まる。
ちなみにこのWZ-pairを用いることで次のような加速級数が導かれます。
$$\z(3)=\frac12\sum^\infty_{n=1}(-1)^{n-1}\frac{205n^2-160n+32}{n^5\binom{2n}n^5}$$
上で求めたWZ-pairに対しZeilbergerの定理
$$\sum^\infty_{n=0}G(n,0)=\sum^\infty_{n=0}(F(n+1,n)+G(n,n))$$
を適用すると
\begin{align}
G(n-1,0)&=(-1)^{n-1}\frac5{2n^3\binom{2n}n}\\
F(n,n-1)&=(-1)^n\frac{3}{2n^3\binom{2n}n^5}\\
G(n-1,n-1)&=(-1)^{n-1}\frac{8(13n^2-10n+2)}{n^5\binom{2n}n^5}
\end{align}
より
前回の記事
の公式1に注意すると
$$\z(3)
=\frac52\sum^\infty_{n=1}\frac{(-1)^{n-1}}{n^3}
=\frac12\sum^\infty_{n=1}(-1)^{n-1}\frac{205n^2-160n+32}{n^5\binom{2n}n^5}$$
を得る。
なお上の例はたまたま上手く計算できただけであり、一般の場合には$A_j(n)$が明示的に、つまり超幾何数列として求まるとは限りません。例えば以下のような問題を考えてみましょう。
$$H(n,k)=\binom nk^3$$
に関するWZ-pairを構成せよ。
具体的な計算はしませんが求める多項式
$$P(n,z)=A_0(n)+A_1(n)k+A_2(n)k^2$$
は
$$\begin{pmatrix}
A_0(n+1)\\A_1(n+1)\\A_2(n+1)
\end{pmatrix}=\begin{pmatrix}
\frac12&\frac{3n+2}4&\frac{3n(n+1)}8\\
-\frac3{2(n+1)}&-\frac{7n+4}{4(n+1)}&-\frac{3n-2}8\\
\frac3{2(n+1)^2}&\frac{3n}{4(n+1)^2}&-\frac{5n+2}{8(n+1)}
\end{pmatrix}\begin{pmatrix}
A_0(n)\\A_1(n)\\A_2(n)
\end{pmatrix}$$
という漸化式によって定まり、対応するWZ-mateは
\begin{align}
G(n,k)=H(n,k)\times\frac{k^3}{8(n+1-k)^3}(
&-4A_0(n)+2A_1(n)(3n+4-2k)\\&+A_2(n)(3n^2-3n-6+6nk+10k-4k^2))
\end{align}
と求まることが知られています。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
