超幾何数列の基礎4：二重数列の総和

方針

　$I,J$を任意に取り$a_{i,j}(n)\in\C[n]$を未知数とする線形方程式
$$\sum^I_{i=0}\sum^J_{j=0}a_{i,j}(n)F(n+i,k+j)=0$$
を考えたとき、両辺を$F(n,k)$で割ることでこの方程式はある多項式$\nu_{i,j}(n,k),\d_{i,j}(n,k)$を用いて
$$\sum^I_{i=0}\sum^J_{j=0}a_{i,j}(n)\frac{\nu_{i,j}(n,k)}{\d_{i,j}(n,k)}=0$$
と表せ、また$\d_{i,j}(n,k)$の最小公倍多項式を$\D(n,k)$とおくと
$$\sum^I_{i=0}\sum^J_{j=0}a_{i,j}(n)\nu_{i,j}(n,k)\frac{\D(n,k)}{\d_{i,j}(n,k)}=0$$
という多項式の恒等式に帰着できる。
　ここでこの左辺の$k$についての次数を$d$とおくと係数比較によってこれは$d+1$本の方程式に分解でき、またこの方程式の未知数の個数は$(I+1)(J+1)$個であるので十分大きい$I,J$に対し
$$d+1<(I+1)(J+1)$$
が成り立つことを示せばよい(一般に方程式の本数より未知数の個数の方が多い線形方程式は非自明な解を持つことが知られている)。

最小公倍多項式

　以下簡単のため$m\geq0$に対し
\begin{align} \rf(x,m)&=(x)_m=x(x+1)\cdots(x+m-1)\\ \ff(x,m)&=\frac1{(x)_{-m}}=(x-1)\cdots(x-m) \end{align}
と定める($\rf,\ff$は上昇階乗(rising factorial)と下降階乗(falling factorial)の頭文字を取っている)。
　このとき
$$\frac{F(n+i,k+j)}{F(n,k)}=\frac{\nu_{i,j}(n,k)}{\d_{i,j}(n,k)}$$
と置いていたので$\nu_{i,j},\d_{i,j}$は
\begin{alignat}{3} \nu_{i,j}(n,k)&=P(n+i,k+j)x^iy^j &&\times\prod^s_{\substack{l=1\\a_li+b_lj>0}}\rf(a_ln+b_lk+c_l,a_li+b_lj)\\ &&&\times\prod^t_{\substack{l=1\\a'_li+b'_lj<0}}\ff(a'_ln+b'_lk+c'_l,|a'_li+b'_lj|)\\ \d_{i,j}(n,k)&=P(n,k) &&\times\prod^s_{\substack{l=1\\a_li+b_lj<0}}\ff(a_ln+b_lk+c_l,|a_li+b_lj|)\\ &&&\times\prod^t_{\substack{l=1\\a'_li+b'_lj>0}}\rf(a'_ln+b'_lk+c'_l,a'_li+b'_lj) \end{alignat}
のように表せる(ただし$\nu_{i,j}/\d_{i,j}$は既約分数とは限らない)。ここで実数$X$に対し
$$X^+=\max\{X,0\},\quad X^-=\max\{-X,0\}$$
と定めたとき
\begin{align} \max\{\a i+\b j\mid 0\leq i\leq I,0\leq j\leq J\}&=\a^+I+\b^+J\\ \min\{\a i+\b j\mid 0\leq i\leq I,0\leq j\leq J\}&=-(\a^-I+\b^-J) \end{align}
が成り立つことに注意すると$\d_{i,j}$の最小公倍多項式は
\begin{alignat}{3} \D(n,k)&=P(n,k) &&\times\prod^s_{l=1}\ff(a_ln+b_lk+c_l,a_l^-i+b_l^-j)\\ &&&\times\prod^t_{l=1}\rf(a'_ln+b'_lk+c'_l,(a'_l)^+i+(b'_l)^+j) \end{alignat}
と求まる。

次数の評価

　このとき
\begin{alignat}{3} \deg\nu_{i,j}(n,k) &\leq\deg P+{}&&\sum^s_{l=1}(a_l^+I+b_l^+J)+\sum^t_{l=1}((a'_l)^-I+(b'_l)^-J)\\ \deg\l(\frac{\D(n,k)}{\d_{i,j}(n,k)}\r) &\leq&&\sum^s_{l=1}(a_l^-I+b_l^-J)+\sum^t_{l=1}((a'_l)^+I+(b'_l)^+J) \end{alignat}
および$X^++X^-=|X|$に注意すると
$$\deg\l(\nu_{i,j}(n,k)\frac{\D(n,k)}{\d_{i,j}(n,k)}\r) \leq\deg P+\sum^s_{l=1}(|a_l|I+|b_l|J)+\sum^t_{l=1}(|a'_l|I+|b'_l|J)$$
が成り立つことがわかる。
　したがって$d$は$I,J$についての一次関数程度の大きさであり、$I,J$が十分大きいときこれは$(I+1)(J+1)-1$より小さいことがわかる。特に
$$A=\sum^s_{l=1}|a_l|+\sum^t_{l=1}|a'_l|,\quad B=\sum^s_{l=1}|b_l|+\sum^t_{l=1}|b'_l|$$
とおき
$$I=B,\quad J=1+\deg P+(A-1)I$$
とすると
\begin{align} d+1 &\leq1+\deg P+AI+BJ\\ &=I+J+IJ\\ &=(I+1)(J+1)-1\\ &<(I+1)(J+1) \end{align}
と所望の不等式が満たされることがわかる。

構成法

　$F$がproperであることから
$$\sum^I_{i=0}\sum^J_{j=0}a_{i,j}(n)F(n+i,k+j)=0$$
なる多項式$a_{i,j}(n)$が取れ、これに対し多項式$P$を
$$P(x,y,z)=\sum^I_{i=0}\sum^J_{j=0}a_{i,j}(x)y^iz^j$$
によって定める。また$N,K$をそれぞれ$n,k$についての前進作用素、つまり数列$f(n,k)$に対して
$$Nf(n,k)=f(n+1,k),\quad Kf(n,k)=f(n,k+1)$$
と定めると
$$P(n,N,K)F(n,k)=0$$
が成り立つことに注意する。
　いま$P$を$z$の多項式として$(1-z)$で割ることで
$$P(x,y,z)=P(x,y,1)+(1-z)Q(x,y,z)$$
と表すと
$$P(n,N,1)F(n,k)=(K-1)Q(n,N,K)F(n,k)$$
が成り立つので
$$G(n,k)=Q(n,N,K)F(n,k),\quad A_i(n)=\sum^J_{j=0}a_{i,j}(n)$$
とおくと
$$\sum^I_{i=0}A_i(n)F(n+i,k)=G(n,k+1)-G(n,k)$$
を得る。また$G$の取り方から$G(n,k)/F(n,k)$は$n,k$についての有理関数となる。

非自明性

　次に$P(x,y,1)\neq1$を満たすような多項式$P(x,y,z)$が存在することを示す。
　いま$P(n,N,K)F(n,k)=0$を満たすような多項式$P(x,y,z)\neq0$であって$z$についての次数が最小となるようなものを取る。このとき$P(x,y,1)=0$が成り立つとすると
$$P(n,N,1)F(n,k)=0=G(n,k+1)-G(n,k)$$
より$G$は$k$に依らない数列となり、またこれは超幾何数列であったことからある$0$でない多項式$B_0(n),B_1(n)$が存在して
$$B_1(n)G(n+1,k)-B_0(n)G(n,k)=0$$
が成り立つ。
　したがって$R(n,N)=B_1(n)N-B_0(n)$とおくと
$$R(n,N)G(n,k)=R(n,N)Q(n,N,K)F(n,k)=0$$
つまり
$$P'(x,y,z)=R(x,y)Q(x,y,z)$$
は$P'(n,N,K)F(n,k)=0$を満たす多項式となるが
$$P(x,y,z)=(1-z)Q(x,y,z)$$
であったことから$P'$は$z$について$P$よりも次数が低い多項式であり、これは$P$の取り方に矛盾。よって$P(x,y,1)\neq0$を得る。

$$F(n,k)=\binom nkx^k,\quad f(n)=\sum_kF(n,k)=\sum^n_{k=0}\binom nk x^k$$
とおく。これは二項係数の漸化式
$$\binom{n+1}k=\binom nk+\binom n{k-1}$$
の両辺に$x^k$を掛けることで
$$F(n+1,k)=F(n,k)+F(n,k-1)x$$
という漸化式を満たすことがわかる。
　したがってこれを$k$について足し合わせることで
$$f(n+1)=(1+x)f(n)$$
という漸化式が得られ、また$f(0)=1$に注意すると
$$f(n)=(1+x)^n$$
と求まる。

$$F(n,k)=\binom nky^n,\quad g(k)=\sum_nF(n,k)=\sum^\infty_{n=k}\binom nk y^n$$
とおくと、これも二項係数の漸化式から
$$F(n+1,k)=F(n,k)y+F(n,k-1)y$$
という漸化式を満たすことがわかる。
　したがってこれを$n$について足し合わせることで
$$g(k)=g(k)y+g(k-1)y$$
つまり
$$g(k)=\frac y{1-y}g(k-1)$$
という漸化式が得られ、また
$$g(0)=\sum^\infty_{n=0}y^n=\frac1{1-y}$$
に注意すると
$$g(k)=\frac{y^k}{(1-y)^{k+1}}$$
と求まる。

$$F(n,k)=\binom nk^2,\quad f(n)=\sum^n_{k=0}\binom nk^2$$
とおきZeilberger's algorithmを実行する。
　とりあえず$I=1$とし
$$\A(k)=A_0(n)\binom nk^2+A_1(n)\binom{n+1}k^2$$
とおく。このとき
\begin{align} \frac{\A(k+1)}{\A(k)} &=\frac{A_0(n)\l(\frac{n-k}{k+1}\r)^2+A_1(n)\l(\frac{n+1}{k+1}\r)^2}{A_0(n)+A_1(n)\l(\frac{n+1}{n+1-k}\r)^2}\\ &=\frac{A_0(n)(n-k)^2+A_1(n)(n+1)^2}{A_0(n)(n+1-k)^2+A_1(n)(n+1)^2}\l(\frac{n+1-k}{k+1}\r)^2 \end{align}
が成り立つので
$$a(k)=(n+1-k)^2,\quad b(k)=(k+1)^2,\quad c(k)=A_0(n)(n+1-k)^2+A_1(n)(n+1)^2$$
とおくとよい。
　このとき
$$(n+1-k)^2x(k+1)-k^2x(k)=A_0(n)(n+1-k)^2+A_1(n)(n+1)^2$$
なる多項式$x(n)$が存在すればその次数は高々$1$であることがわかるので
$$x(n)=B_0(n)+B_1(n)k$$
とおくと$k$についての係数比較によって
\begin{align} (B_0+B_1)-2(n+1)B_1-B_0&=A_0\\ -2(n+1)(B_0+B_1)+(n+1)^2B_1&=-2(n+1)A_0\\ (n+1)^2(B_0+B_1)&=(n+1)^2(A_0+A_1) \end{align}
つまり
$$\begin{pmatrix} 1&0&0&2n+1\\ 2&0&-2&n-1\\ 1&1&-1&-1 \end{pmatrix}\begin{pmatrix} A_0\\A_1\\B_0\\B_1 \end{pmatrix}=\begin{pmatrix} 0\\0\\0\\0 \end{pmatrix}$$
という方程式が得られるので、これを解くことでその解の一つとして
$$A_0=-2(2n+1),\quad A_1=n+1,\quad B_0=-3(n+1),\quad B_1=2$$
と求まる。
　以上より
$$A_1(n)f(n+1)+A_0(n)f(n)=(n+1)f(n+1)-2(2n+1)f(n)=0$$
という漸化式が得られ、また$f(0)=1$に注意すると
$$f(n)=\frac{2n(2n-1)}{n^2}f(n-1)=\frac{(2n)!}{(n!)^2}f(0)=\binom{2n}n$$
と求まる。
　ちなみにこのとき
$$x(k)=B_1k+B_0=2k-3n-3$$
であったのでこれによって$G(n,k)$は
$$G(n,k)=\frac{k^2(2k-3n-3)}{(n-k+1)^2}F(n,k)$$
と求まる。またこの問題をSister Celine's algorithmによって解く場合は
\begin{align} nF(n,k)&-(2n-1)(F(n-1,k)+F(n-1,k-1))\\ &+(n-1)(F(n-2,k)-2F(n-2,k-1)+F(n-2,k-2))=0 \end{align}
という漸化式が得られる。