超幾何数列の基礎8：簡約化の応用
はじめに
この記事では
前回の記事
に引き続き超幾何数列の基本事項についてまとめていきます。
第四回の記事では(properな) 超幾何数列$F(n,k)$に対し
$$\sum^I_{i=0}p_i(n)F(n+i,k)=G(n,k+1)-G(n,k)$$
なる多項式$p_i(n)$と超幾何数列$G(n,k)$を構成することで
$$f(n)=\sum_kF(n,k)$$
に関する漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=0$$
を求める手法：Zeilberger's methodについて解説しました。
今回の記事ではZeilberger's methodに対する
前回の記事
にて紹介した簡約化を用いたアプローチについて解説していきます。
Chen-Huang-Kauers-Li's Method
やることとしては単純で結論から言うとこの問題は次のようなアルゴリズムによって解決することができます。
- 変数$k$に注目し
Abramov-Petkovšek's algorithm
を実行することで
$$F(n+i,k)=G_i(n,k+1)-G_i(n,k)+T_i(n,k)$$
なるresidual form$T_i(n,k)$であって、任意の多項式$p_0(n),\ldots,p_I(n)$に対し
$$\sum^I_{i=0}p_i(n)T_i(n,k)$$
も($0$でなければ)residual formとなるようなものを求める。 - $I$を十分大きく取り、未知の多項式$p_0(n),\ldots,p_I(n)$に関する線形方程式
$$\sum^I_{i=0}p_i(n)T_i(n,k)=0$$
を解く。 - このとき
$$G(n,k)=\sum^I_{i=0}p_i(n)G_i(n,k)$$
とおくと
$$\sum^I_{i=0}p_i(n)F(n+i,k)=G(n,k+1)-G(n,k)$$
が成り立つ。
要するに「residual formはGosper総和不可能である」という事実を上手く利用しているわけですね。
residual formの和
ではこのアルゴリズムの詳細を詰めるためにステップ1における$T_i(n,k)$の構成法について考えていきましょう。
まずはこれらの核$K(k)$を固定して殻についての話に帰着させておきましょう。
$K(n)=p(n)/q(n)$をshift-reducedな有理関数とする。
このとき有理関数
$$R(n)=\frac{a(n)}{v(n)}+\frac{b(n)}{q(n)}$$
が$K(n)$に関するresidual formであるとは、これらが以下の条件を満たすことを言う。
- $v(n)$はshit-free
- $v(n)$と$K(n)$はstrongly coprime
- $\deg a<\deg v$
- $b(n)\in W_K$
いま有理関数$R(n),R'(n)$が共に$K(n)$に関するresidual formであっても$R(n)+R'(n)$が再びresidual formとなるとは限りません。しかし分母を適当に平行移動することで次の場合に帰着させることができます。
$K(n)$に関するresidual form
$$R(n)=\frac{a(n)}{v(n)}+\frac{b(n)}{q(n)},\quad
R'(n)=\frac{a'(n)}{v'(n)}+\frac{b'(n)}{q(n)}$$
が任意の整数$h\neq0$に対し
$$\gcd(v(n),v'(n+h))=1$$
を満たすとき$R(n)+R'(n)$は($0$でなければ)再びresidual formとなる。
$W_K$の線形性より$b(n)+b'(n)\in W_K$となるので、あとは
$$\frac{\a(n)}{\nu(n)}=\frac{a(n)}{v(n)}+\frac{a'(n)}{v'(n)}$$
とおき、これが(i),(ii),(iii)を満たすことを確かめるだけである(証明略)。
実際ある$h\neq0$に対し$v(n),v'(n+h)$が既約多項式$b(n)$で割り切れるとき、$R'(n)$を適当に部分分数分解し
前回の記事
の補題5の証明のようにして
$$\frac{a_h(n)}{b(n-h)^k}=K(n)g(n+1)-g(n)+\l(\frac{c_0(n)}{b(n)^l}+\frac{c_1(n)}{q(n)}\r)$$
と平行移動させることで$\gcd(v(n),v'(n+h))=1$となるように変形することができます。
つまりステップ2の操作において$T_i(n,k)$は、その殻$R_i(k)$が以下の条件を満たすように取ればいいことになります。
$K(k)$についてのresidual form
$$R_i(k)=\frac{a_i(k)}{v_i(k)}+\frac{b_i(k)}{q(k)}$$
が任意の整数$h\neq0$および$i,j$に対し
$$\gcd(v_i(k),v_j(k+h))=1$$
を満たすとき、任意の$p_0,\ldots,p_I$に対し
$$\sum^I_{i=0}p_iR_i(k)$$
は($0$でなければ)再びresidual formとなる。
Chen-Huang-Kauers-Li's Algorithm
以上のことを踏まえると上のアルゴリズムは以下のように詳細化できます。
- $F(n,k)$の$k$についての核と殻$K(n,k),S(n,k)$を一つ取り
$$F(n,k)=S(n,k)H(n,k)$$
および
$$N(n,k)=\frac{H(n+1,k)}{H(n,k)}\qquad \l(\mathrm{cf.}\ K(n,k)=\frac{H(n,k+1)}{H(n,k)}\r)$$
とおく。 - 各$i$に対し
$$\frac{F(n+i,k)}{H(n,k)}=K(n,k)S_i(n,k+1)-S_i(n,k)+R_i(n,k)$$
なる$K(n,k)$に関するresidual form$R_i(n,k)$であって定理2の仮定を満たすようなものを求めていく。このとき
\begin{align} N(n,k)R_i(n+1,k)&=K(n,k)S'_{i+1}(n,k+1)-S'_{i+1}(n,k)+R_{i+1}(n,k)\\ (S'_{i+1}(n,k)&=S_{i+1}(n,k)-N(n,k)S_i(n+1,k)) \end{align}
という関係を用いて回帰的に$R_{i+1}$を求めていくのも効果的である。 - $I$を十分大きく取り、未知の多項式$p_0(n),\ldots,p_I(n)$に関する線形方程式
$$\sum^I_{i=0}p_i(n)R_i(n,k)=0$$
を解く。 - このとき
$$G(n,k)=\l(\sum^I_{i=0}p_i(n)S_i(n,k)\r)H(n,k)$$
とおくと
$$\sum^I_{i=0}p_i(n)F(n+i,k)=G(n,k+1)-G(n,k)$$
が成り立つ。
計算例
では実際の計算例を見ていきましょう。
$$f(n)=\sum^n_{k=0}\binom nk x^k$$
を閉形式に表せ。
解説
$$F(n,k)=\binom nk x^k$$
の核と殻として
$$K(k)=\frac{n-k}{k+1}x,\quad S(k)=1=\frac{k+1}{k+1}$$
を取る。このとき
$$K(k)-1=\frac{n+1}{k+1}x-(x+1)$$
に注意して
\begin{align}
S_0(k)&=-\frac1{x+1}\\
S_1(k)&=-\frac{n+1}{n-k+1}
\end{align}
とおくと
\begin{align}
S(k)&=K(k)S_0(k+1)-S_0(k)+\frac{n+1}{k+1}\frac x{x+1}\\
\frac{F(n+1,k)}{F(n,k)}&=K(k)S_1(k+1)-S_1(k)+\frac{n+1}{k+1}x
\end{align}
と変形できる。
したがって
\begin{align}
G(n,k)
&=(S_1(k)-(x+1)S_0(k))F(n,k)\\
&=-\binom n{k-1}x^k
\end{align}
とおくと
$$F(n+1,k)-(x+1)F(n,k)=G(n,k+1)-G(n,k)$$
が成り立つ。
したがってこれを$k$について足し合わせることで漸化式
$$f(n+1)-(x+1)f(n)=0$$
が得られ、$f(0)=1$に注意すると
$$f(n)=(x+1)^n$$
と求まる。
$$f(n)=\sum^n_{k=0}\binom nk^2$$
を閉形式に表せ。
解説
$$F(n,k)=\binom nk^2$$
の核と殻として
\begin{align}
K(k)&=\frac{(n-k)^2}{(k+1)^2}\\
&=\frac{(n+1)^2}{(k+1)^2}-\frac{2(n+1)}{k+1}+1\\
S(k)&=1=\frac{(k+1)^2}{(k+1)^2}
\end{align}
を取る。このとき
\begin{align}
K(k)-1&=\frac{(n+1)^2}{(k+1)^2}-\frac{2(n+1)}{k+1}\\
K(k)(k+1)-k&=\frac{(n+1)^2}{k+1}-(2n+1)
\end{align}
が成り立つことに注意し
\begin{align}
S_0(k)&=-\frac1{2n+1}\l(k+\frac{n+1}2\r)\\
S_1(k)&=-\frac{(n+1)^2}{(n-k+1)^2}
\end{align}
とおくと
\begin{align}
S(k)&=K(k)S_0(k+1)-S_0(k)+\frac{n+1}{2(2n+1)}\frac{(n+1)^2}{(k+1)^2}\\
\frac{F(n+1,k)}{F(n,k)}&=K(k)S_1(k+1)-S_1(k)+\frac{(n+1)^2}{(k+1)^2}
\end{align}
と変形できる。
したがって
\begin{align}
G(n,k)
&=((n+1)S_1(k)-2(2n+1)S_0(k))F(n,k)\\
&=-(3n-2k+3)\binom n{k-1}^2
\end{align}
とおくと
$$(n+1)F(n+1,k)-2(2n+1)F(n,k)=G(n,k+1)-G(n,k)$$
が成り立ち、これを$k$について足し合わせることで
$$f(n)=\sum^n_{k=0}\binom nk^2$$
についての漸化式
$$(n+1)f(n+1)-2(2n+1)f(n)=0$$
が得られる。また$f(0)$に注意すると
$$f(n)=\frac{2n(2n-1)}{n^2}f(n-1)=\frac{(2n)!}{(n!)^2}f(0)=\binom{2n}n$$
を求まる。
Zeilberger's algorithm
による解法だと
$$\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}$$
という煩雑な線形方程式を導出および求解しなければなりませんでしたが、今回の記事における手法ではこのように
$$\l(p_1(n)+p_0(n)\frac{n+1}{2(2n+1)}\r)\frac{(n+1)^2}{(k+1)^2}=0$$
という($p_0(n),p_1(n)$についての)簡単な方程式に帰着でき、計算が非常に楽であることが実感できますね。
$$f(n)=\sum^n_{k=0}\binom nk^3$$
の満たす漸化式を求めよ。
解説
$$F(n,k)=\binom nk^3$$
の核と殻として
\begin{align}
K(k)&=\frac{(n-k)^3}{(k+1)^3}\\
&=\frac{(n+1)^3}{(k+1)^3}-\frac{3(n+1)^2}{(k+1)^2}+\frac{3(n+1)}{k+1}-1\\
S(k)&=1=\frac{(k+1)^3}{(k+1)^3}
\end{align}
を取る。このとき
\begin{align}
S_0(k)&=-\frac12\\
S_1(k)&=-\frac{(n+1)^3}{(n-k+1)^3}\\
S'_2(k)&=-\frac{(n+1)^3}{(n+2)^2}\frac{(n+2)^2+3(n+2)(n-k+1)+6(n-k+1)^2}{(n-k+1)^3}
\end{align}
とおくと
\begin{align}
S(k)&=K(k)S_0(k+1)-S_0(k)
+\frac12\l(\frac{(n+1)^3}{(k+1)^3}-\frac{3(n+1)^2}{(k+1)^2}+\frac{3(n+1)}{k+1}\r)\\
\frac{F(n+1,k)}{F(n,k)}&=K(k)S_1(k+1)-S_1(k)+\frac{(n+1)^3}{(k+1)^3}\\
\frac{(n+2)^3}{(k+1)^3}\frac{F(n+1,k)}{F(n,k)}
&=\frac{(n+1)^3}{(n+2)^2}\l(\frac{(n+2)^2+3(n+2)(k+1)+6(k+1)^2}{(k+1)^3}+\frac{(n+2)^2+3(n+2)(n-k+1)+6(n-k+1)^2}{(n-k+1)^3}\r)\\
&=K(k)S'_2(k+1)-S'_2(k)\\
&\quad+\frac{(n+1)^3}{(n+2)^2}\l(\frac{(n+2)^2+3(n+2)(k+1)+6(k+1)^2}{(k+1)^3}+\frac{(n+2)^2+3(n+2)(n-k)+6(n-k)^2}{(k+1)^3}\r)\\
&=K(k)S'_2(k+1)-S'_2(k)
+\frac{(n+1)^3}{(n+2)^2}\l(\frac{11n^2+29n+20}{(k+1)^3}-\frac{12(n+1)}{(k+1)^2}+\frac{12}{k+1}\r)
\end{align}
が成り立つので$p_0(n),p_1(n),p_2(n)$についての方程式
\begin{align}
0={}&p_2(n)\frac{(n+1)^3}{(n+2)^2}\l(\frac{11n^2+29n+20}{(k+1)^3}-\frac{12(n+1)}{(k+1)^2}+\frac{12}{k+1}\r)\\
&+p_1(n)\frac{(n+1)^3}{(k+1)^3}\\
&+p_0(n)\frac12\l(\frac{(n+1)^3}{(k+1)^3}-\frac{3(n+1)^2}{(k+1)^2}+\frac{3(n+1)}{k+1}\r)
\end{align}
を解くことで
$$(n+2)^2f(n+2)-(7n^2+21n+16)f(n+1)+8(n+1)^2f(n)=0$$
という漸化式が得られる。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
