この記事では
前回の記事
に引き続き超幾何数列の基本事項についてまとめていきます。
前回の記事ではproperな超幾何数列$F(n,k)$に対して
$$\sum^I_{i=0}p_i(n)F(n+i,k)=G(n,k+1)-G(n,k)$$
というタイプのcreative telescopingができることを示しました。そして今回の記事ではこの最たる例として
$$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$
というタイプのcreative telescopingができる場合に関する手法Wilf-Zeilberger method、略してWZ methodについて解説していきます。
いま(properな)超幾何数列$A(n),F(n,k)$についての等式
$$\sum_kF(n,k)=A(n)$$
があったとしましょう。このときこの右辺は一階の漸化式
$$f(n+1)-\frac{A(n+1)}{A(n)}f(n)=0$$
を満たすので、Zeilberger's methodによって得られる
$$\sum^I_{i=0}p_i(n)F(n+i,k)=G(n,k+1)-G(n,k)$$
という$F(n,k)$に関する漸化式も
$$F(n+1,k)-\frac{A(n+1)}{A(n)}F(n,k)=G(n,k+1)-G(n,k)$$
のような形になると期待できます。
そして、驚くべきことに、実際それが多くの場合において成り立つということが経験的な事実として知られています。特にこのとき
$$\ol F(n,k)=\frac{F(n,k)}{A(n)},\quad \ol G(n,k)=\frac{G(n,k)}{A(n+1)}$$
とおくと
$$\ol F(n+1,k)-\ol F(n,k)=\ol G(n,k+1)-\ol G(n,k)$$
という等式が成り立つことに注意しましょう。
このように
$$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$
を満たすような超幾何数列の組$F,G$を構成することで
$$\sum_k F(n,k)=1$$
のような等式を示す手法のことをWZ methodと言います。
$2$つの超幾何数列$F(n,k),G(n,k)$がWZ-pairであるとは
$$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$
を満たすことを言う。
ちなみに$F(n,k)$に対してパートナーとなる$G(n,k)$のことをWZ-mateと言うことがあります。
いま与えられた超幾何数列$F(n,k)$に対してWZ methodが適用できるのかどうか、そしてそのときWZ-mate$G(n,k)$はどうやって求められるのかについては
$$A(k)=F(n+1,k)-F(n,k)$$
に対して
Gosper's algorithm
を実行するだけで解決します。
また上での議論を踏まえると与えられた超幾何数列$F(n,k)$に対してあるWZ-pair$\ol F,\ol G$を構成する方法として次のようなものが考えられます。
またWZ-pairの構成に関するより一般的な方法としてMarkov-WZ methodというものも知られていますがそれについては 次回の記事 にて詳しく解説しようと思います。
$$F(n,k)=\binom nk^2$$
に関するWZ-pairを構成せよ。
前回の記事
の問題3から
$$G(n,k)=\frac{k^2(2k-3n-3)}{(n-k+1)^2}F(n,k)$$
とおくと
$$(n+1)F(n+1,k)-2(2n+1)F(n,k)=G(n,k+1)-G(n,k)$$
が成り立つのであった。
したがって
$$A(n)=\binom{2n}n$$
および
$$\ol F(n,k)=\frac{F(n,k)}{A(n)},\quad\ol G(n,k)=\frac{G(n,k)}{2(2n+1)A(n)}$$
とおくとこれはWZ-pairとなる。
$$F(n,k)=\l(\frac{n!k!}{(n+k)!}\r)^2$$
に関するWZ-pairを構成せよ。
前回の記事
の問題3と同様にして
$$(k+1)^2x(k+1)-(n+1+k)^2x(k)=(n+1+k)^2A_0+(n+1)^2A_1$$
という方程式が得られ
$$x(k)=B_0+B_1k$$
とおき$(k+1)$について係数比較することでその解の一つとして
$$A_0=-2(2n-1),\quad A_1=\frac{n^3}{(n+1)^2},\quad B_0=3n,\quad B_1=2$$
と求まる。このとき
$$G(n,k)=(2k+3n)F(n,k)$$
が成り立つ。
また
$$A(n+1)=-\frac{A_0}{A_1}A(n)=\frac{(n+1)^2}{n^3}2(2n-1)A(n)$$
を解くと$A(1)=1$において
$$A(n)=\frac{n^3}{2(2n-1)}\binom{2n}n$$
と求まるので
\begin{alignat}{3}
\ol F(n,k)
&=\frac{F(n,k)}{A(n)}
&&=\frac{2(2n-1)}{n^3\binom{2n}n}F(n,k)\\
\ol G(n,k)
&=\frac{G(n,k)}{2(2n-1)A(n)}
&&=\frac{2k+3n}{n^3\binom{2n}n}F(n,k)
\end{alignat}
とおくとこれはWZ-pairとなる。
上でも言及したようにWZ methodの基本的な使い方として
$$f(n)=\sum_kF(n,k)=\mathrm{Const.}$$
というタイプの等式を示すことが挙げられます。
このような等式は
$$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$
の両辺を$k$について足し合わせたとき、右辺の和が
$$\sum^\infty_{k=-\infty}(G(n,k+1)-G(n,k))=G(n,\infty)-G(n,-\infty)=0$$
となることを仮定すれば
$$f(n+1)-f(n)=0$$
が成り立つことから導けます。
ところでproperな超幾何数列とは
$$F(n,k)=P(n,k)\frac{\prod^s_{j=1}\G(a_jn+b_jk+c_j)}{\prod^t_{j=1}\G(a'_jn+b'_jk+c'_j)}x^ny^k$$
と表せるようなもののことを言うのでした。ここで適当な条件下においてこの右辺を$n\in\C$についての複素関数に拡張すると上の結果
$$\sum_kF(n,k)=\mathrm{Const.}\qquad(n=0,1,2,\ldots)$$
から
$$\sum_kF(n,k)=\mathrm{Const.}\qquad(n\in\C)$$
を導くことができます。
これはCarlsonの定理から直ちに従います。
$\Re(z)\geq0$における正則関数$f$が
を満たすとき、$f$は恒等的に$0$となる。
仮定より$f(s)$に対し
Ramanujan's Master Theorem
が適用できる。つまり
$$\Phi(x)=\frac1{2\pi i}\int^{c+i\infty}_{c-i\infty}\frac\pi{\sin\pi s}f(-s)x^{-s}ds$$
とおくと$x=0$の近傍で
$$\Phi(x)=\sum^\infty_{n=0}f(n)(-x)^n=0$$
が成り立つので$\Phi(x)$は恒等的に$0$であり、またある領域において
$$f(-s)=\frac{\sin\pi s}\pi\int^\infty_0\Phi(x)x^{s-1}dx=0$$
が成り立つので$f(z)$は恒等的に$0$となる。
いま$n$を複素数とできることによって特殊値が確認しやすくなるという嬉しさが発生します。
例えば$F(n,k)$が
$$\frac1{\G(n-k+c)}\qquad(c\not\in\Z)$$
という因子を持つとき、$n\in\Z$の範囲であればこれはうんともすんとも言いませんが、$n\in\C$の範囲であれば$n=1-c$とすることでこれは$k\geq1$において$0$となるので
$$\sum^\infty_{k=0}F(1-c,k)=F(1-c,0)$$
と求まり、したがって任意の$n\in\C$に対して
$$\sum^\infty_{k=0}F(n,k)=F(1-c,0)$$
が成り立つ、といった議論をすることができます。
またWZ methodのもう一つの使い方として級数同士の等式
$$\sum_nG(n,k)=\sum_nG'(n,k)$$
を量産するということが挙げられます。
これにはWZ-pairのなす差分形式というものがいわゆる"渦なし"であることが重要となります。
差分形式
$$\o=G(n,k)\d n+F(n,k)\d k$$
に対し、グリッド上の単位経路
\begin{align}
C_n&:(n,k)\to(n+1,k\phantom{{}+1})\\
C_k&:(n,k)\to(n\phantom{{}+1},k+1)
\end{align}
における和分を
$$\sum_{C_n}\o=G(n,k),\quad\sum_{C_k}\o=F(n,k)$$
によって定める。
差分形式
$$\o=F(n,k)\d k+G(n,k)\d n$$
がWZ形式(WZ form)であるとは$F,G$がWZ-pairであることを言う。
WZ form$\o$と任意の閉経路$C$に対し
$$\sum_C\o=0$$
が成り立つ。
単位正方形に分割することによって経路
$$C:(n,k)\to(n+1,k)\to(n+1,k+1)\to(n,k+1)\to(n,k)$$
の場合について示せば十分であり、その場合は
$$\sum_C\o=G(n,k)+F(n+1,k)-G(n,k+1)-F(n,k)=0$$
とわかる。
このことは渦なし場
$$\boldsymbol r=(v(x,y),u(x,y))\quad
\l(\frac{\partial u}{\partial x}=\frac{\partial v}{\partial y}\r)$$
においてGreenの定理より
$$\oint_C\boldsymbol r\cdot d\boldsymbol x=\oint_C(vdx+udy)=0$$
が成り立つことの類似となっています。
ちなみにより一般的な事実として
離散版Stokesの定理
というものも知られています。
いま適当な閉経路における和分を考えることで例えば次のような変換公式が得られます。
WZ-pair$F,G$が
$$\lim_{n\to\infty}\sum^{n-1}_{n_0=0}F(n,k+n_0)=0$$
を満たすとき
$$\sum^\infty_{n=0}G(n,k)=\sum^\infty_{n=0}(F(n+1,n+k)+G(n,n+k))$$
が成り立つ。
階段状の閉経路$C=C_1+C_2-C_3$
\begin{align}
C_1&:(0,k)\to(1,k)\to(2,k)\to\cdots\to(n,k)\\
C_2&:(n,k)\to(n,k+1)\to(n,k+2)\to\cdots\to(n,k+n)\\
C_3&:(0,k)\to(1,k)\to(1,k+1)\to(2,k+1)\to(2,k+2)\to\cdots\to(n,k+n)
\end{align}
を考えると
\begin{align}
\sum_{C_1}\o&=\sum^{n-1}_{n_0=0}G(n_0,k)\\
\sum_{C_2}\o&=\sum^{n-1}_{n_0=0}F(n,k+n_0)\\
\sum_{C_3}\o&=\sum^{n-1}_{n_0=0}(F(n_0+1,k+n_0)+G(n_0,k+n_0))
\end{align}
が成り立つことからわかる。
またこの階段の各辺の長さを変えることでこの公式は次のように一般化できます。
WZ-pair$F,G$が
$$\lim_{n\to\infty}\sum^\infty_{k=0}F(n,k)=0$$
を満たすとき、任意の正整数$p,q$に対し
$$\sum^\infty_{n=0}G(n,0)
=\sum^\infty_{n=0}\l(\sum^{q-1}_{j=0}F(pn,qn+j)+\sum^{p-1}_{j=0}G(pn+j,q(n+1))\r)$$
が成り立つ。
例えば
\begin{align}
\sum^\infty_{n=0}G(n,0)
&=\sum^\infty_{n=0}(F(n,n)+G(n,n+1))\\
&=\sum^\infty_{n=0}(F(n,2n)+F(n,2n+1)+G(n,2n+2))\\
&=\sum^\infty_{n=0}(F(n,3n)+F(n,3n+1)+F(n,3n+2)+G(n,3n+3))\\
&=\sum^\infty_{n=0}(F(2n,2n)+F(2n,2n+1)+G(2n,2n+2)+G(2n+1,2n+2))
\end{align}
のような式が成り立ちます。
他にも様々な経路の取り方を考えることで色々な変換公式が得られます。例えば次のような有限和の等式なども興味深いですね。
WZ-pair$F,G$に対し
$$\sum^n_{k=0}F(n,k)=F(0,0)+\sum^n_{k=1}(F(k,k)+G(k-1,k)+G(k-1,0))$$
が成り立つ。
経路$(0,0)\to(n,n+1)$における和分を二通りに計算するだけである。
さて御託を並べるのはこのくらいにして、ここからは実際の応用例について見ていくこととしましょう。
まずはラマヌジャンの円周率公式、の中でも簡単なもの
$$\frac2\pi=\sum^\infty_{k=0}(-1)^k(4k+1)\frac{(\frac12)_k^3}{(1)_k^3}$$
を証明してみましょう。
これはEkhad-Zeilbergerによって次のように一般化されています。
$$\frac{(1)_n}{(\frac12)_n}\cdot\frac2\pi =\sum^\infty_{k=0}(-1)^k(4k+1)\frac{(\frac12)_k^2(\frac12-n)_k}{(1)_k^2(1+n)_k}$$
\begin{align}
F(n,k)&=(-1)^k(4k+1)\frac{(\frac12)_k^2(\frac12-n)_k}{(1)_k^2(1+n)_k}\frac{(\frac12)_n}{(1)_n}\\
G(n,k)&=\frac{(2k+1)^2}{2(n+k+1)(4k+1)}F(n,k)
\end{align}
とおくとこれはWZ-pairとなる。したがって
$$\sum^\infty_{k=0}F(n,k)=\mathrm{Const.}$$
であり$n=\frac12$とすると
$$(\tfrac12-n)_k=(0)_k=\l\{\begin{array}{ll}
1&k=0\\
0&k\neq0
\end{array}\r.$$
となるので$(x)_n=\G(x+n)/\G(n)$に注意すると
\begin{align}
\sum^\infty_{k=0}F(n,k)
&=\sum^\infty_{k=0}F(\tfrac12,k)\\
&=\frac{\G(\frac12+\frac12)}{\G(\frac12)\G(1+\frac12)}\\
&=\frac2\pi
\end{align}
を得る。
ちなみにその他の円周率公式にも同様の一般化が得られており、それらの公式については この記事 にてそれとなくまとめています。
次にApéryによる$\z(3)$の無理性の証明に使われたことでも有名な公式
$$\z(3)=\frac52\sum^\infty_{n=1}\frac{(-1)^{n-1}}{n^3\binom{2n}n}$$
をWZ methodによって証明してみましょう。
\begin{align}
H(n,k)&=(-1)^k\frac{(k!)^2(n-k)!}{(n+k)!}=\frac{(-1)^k}{\binom nk\binom{n+k}k}\\
F(n,k)&=\frac1{2k^3}H(n,k)\\
G(n,k)&=\frac{n-k+1}{k^2(n+1)^2}H(n,k)
\end{align}
というWZ-pairに対しZeilbergerの定理
$$\sum^\infty_{n=1}G(n-1,1)=\sum^\infty_{n=1}(F(n,n)+G(n-1,n))$$
を適用すると
\begin{align}
G(n-1,1)&=-\frac1{n^3}\\
F(n,n)&=\frac12\frac{(-1)^n}{n^3\binom{2n}n}\\
G(n-1,n)&=2\frac{(-1)^n}{n^3\binom{2n}n}
\end{align}
が成り立つことからわかる。
また類似のWZ-pairを用いることで$\z(2)$に関する次のような公式が得られます。
$$\z(2)=\sum^\infty_{n=1}\frac3{n^2\binom{2n}n}$$
\begin{align}
H(n,k)&=(-1)^{n+k}\frac{(k!)^2(n-k)!}{(n+k)!}=\frac{(-1)^{n+k}}{\binom nk\binom{n+k}k}\\
F(n,k)&=\frac1{2k^2}H(n,k)\\
G(n,k)&=\frac{n-k+1}{k^2(n+1)}H(n,k)
\end{align}
というWZ-pairに対しZeilbergerの定理
$$\sum^\infty_{n=1}G(n-1,1)=\sum^\infty_{n=1}(F(n,n)+G(n-1,n))$$
を適用すると
\begin{align}
G(n-1,1)&=(-1)^n\frac1{n^2}\\
F(n,n)&=\frac12\frac1{n^2\binom{2n}n}\\
G(n-1,n)&=-2\frac1{n^2\binom{2n}n}
\end{align}
より
$$\sum^\infty_{n=1}\frac{(-1)^{n-1}}{n^2}=\frac32\sum^\infty_{n=1}\frac1{n^2\binom{2n}n}$$
が得られる。また
$$\sum^\infty_{n=1}\frac{(-1)^{n-1}}{n^2}=(1-2^{1-2})\z(2)=\frac12\z(2)$$
に注意すると主張を得る。
さらに上の問題2として求めたWZ-pair
\begin{align}
H(n,k)&=\l(\frac{n!k!}{(n+k)!}\r)^2\\
F(n,k)&=\frac{2(2n-1)}{n^3\binom{2n}n}H(n,k)\\
G(n,k)&=\frac{2k+3n}{n^3\binom{2n}n}H(n,k)
\end{align}
を用いると次のような公式が導かれます。
$$\z(2)=\sum^\infty_{n=1}\frac{21n-8}{n^3\binom{2n}n^3}$$
上のWZ-pairに対しZeilbergerの定理
$$\sum^\infty_{n=1}G(n,0)=\sum^\infty_{n=1}(F(n,n-1)+G(n,n))$$
を適用すると
\begin{align}
G(n,0)&=\frac{3}{n^2\binom{2n}n}\\
F(n,n-1)&=\frac{8(4n-1)}{n^3\binom{2n}n^3}\\
G(n,n)&=\frac{5n}{n^3\binom{2n}n^3}
\end{align}
が成り立つことおよび公式3からわかる。
以上がWZ methodの概要となります。
見ての通りWZ methodは自由変数のある与えられた級数
$$\sum^\infty_{k=0}F(n,k),\quad\sum^\infty_{n=0}G(n,k)$$
の値を求めたり加速級数に変形したりするのには使えますが、自由変数のない級数
$$\sum^\infty_{k=0}A(k)$$
に対して適当なWZ-pairを探し出し、その性質を調べようとするのには向いていないと思います。
ただそのような点に目を瞑れば、WZ methodは主に超幾何関数にまつわる多くの等式を(機械的に)示す上で非常に重要な手法であり、また無作為に取ってきた超幾何数列$H$に対してWZ-pair$F,G$を構成してみるだけでも色々と非自明な等式が現れて面白いので、皆さんも色々なWZ methodの例に触れて遊んでみてはいかがでしょうか。
私もWZ methodについてそこまで詳しいわけではないので、また面白い話を見かけたら続きの記事でも書こうと思います。とりあえず個人的に掲げていた「WZ methodについて解説する」という目標は達成できたので今回のシリーズはこんなところで。
では。
ところでWZ form
$$\o=F(n,k)\d k+G(n,k)\d n$$
とはいわゆる"渦なし"の差分形式であったのでこれに関するポテンシャルという概念を考えることができます。
数列$c(n,k)$がWZ form
$$\o=F(n,k)\d k+G(n,k)\d n$$
のポテンシャルであるとは、その偏差分が
\begin{align}
c(n,k+1)-c(n,k)&=F(n,k)\\
c(n+1,k)-c(n,k)&=G(n,k)
\end{align}
を満たすことを言う。
特に経路$C:(0,0)\to(n,k)$における不定和分が定める関数
$$c(n,k)=\sum_C\o$$
は$\o$のポテンシャルの一つとなります。
また逆に任意に数列$c(n,k)$を持ってきたとき、その"勾配"
\begin{align}
F(n,k)&=c(n,k+1)-c(n,k)\\
G(n,k)&=c(n+1,k)-c(n,k)
\end{align}
を取るとこれらは
$$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$
を満たします。
特に$c(n,k)$をあるWZ form$\o$のポテンシャルとし
$$c'(n,k)=c(pn+qk,rn+sk),\quad(p,q,r,s\in\Z)$$
という関数の"勾配"を考えることで新たなWZ-pairを構成することができます。
例えば
$$c'(n,k)=c(n,n+k)$$
とおくと
\begin{align}
c'(n,k+1)-c'(n,k)
&=c(n,n+k+1)-c(n,n+k)\\
&=F(n,n+k)\\
c'(n+1,k)-c'(n,k)
&=c(n+1,n+k+1)-(c(n+1,n+k)-c(n+1,n+k))-c(n,n+k)\\
&=F(n+1,n+k)+G(n,n+k)
\end{align}
より
\begin{align}
F_1(n,k)&=F(n,n+k)\\
G_1(n,k)&=F(n+1,n+k)+G(n,n+k)
\end{align}
というWZ-pairが得られます。
だから何だという感じではありますが、たまに役に立つので豆知識程度に覚えておくといいと思います。