文献あり

超幾何数列の基礎8：簡約化の応用

168

はじめに

　この記事では前回の記事に引き続き超幾何数列の基本事項についてまとめていきます。
　第四回の記事では(properな) 超幾何数列 $F (n, k)$ に対し
$\sum_{i = 0}^{I} p_{i} (n) F (n + i, k) = G (n, k + 1) - G (n, k)$
なる多項式 $p_{i} (n)$ と超幾何数列 $G (n, k)$ を構成することで
$f (n) = \sum_{k} F (n, k)$
に関する漸化式
$\sum_{i = 0}^{I} 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), \dots, p_{I} (n)$ に対し
$\sum_{i = 0}^{I} p_{i} (n) T_{i} (n, k)$
も( $0$ でなければ)residual formとなるようなものを求める。
$I$ を十分大きく取り、未知の多項式 $p_{0} (n), \dots, p_{I} (n)$ に関する線形方程式
$\sum_{i = 0}^{I} p_{i} (n) T_{i} (n, k) = 0$
を解く。
このとき
$G (n, k) = \sum_{i = 0}^{I} p_{i} (n) G_{i} (n, k)$
とおくと
$\sum_{i = 0}^{I} 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)}, R^{'} (n) = \frac{a^{'} (n)}{v^{'} (n)} + \frac{b^{'} (n)}{q (n)}$
が任意の整数 $h \neq 0$ に対し
$gcd (v (n), v^{'} (n + h)) = 1$
を満たすとき $R (n) + R^{'} (n)$ は( $0$ でなければ)再びresidual formとなる。

　 $W_{K}$ の線形性より $b (n) + b^{'} (n) \in W_{K}$ となるので、あとは
$\frac{α (n)}{ν (n)} = \frac{a (n)}{v (n)} + \frac{a^{'} (n)}{v^{'} (n)}$
とおき、これが(i),(ii),(iii)を満たすことを確かめるだけである(証明略)。

　実際ある $h \neq 0$ に対し $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) + (\frac{c_{0} (n)}{b (n)^{l}} + \frac{c_{1} (n)}{q (n)})$
と平行移動させることで $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 \neq 0$ および $i, j$ に対し
$gcd (v_{i} (k), v_{j} (k + h)) = 1$
を満たすとき、任意の $p_{0}, \dots, p_{I}$ に対し
$\sum_{i = 0}^{I} p_{i} R_{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)} (cf . K (n, k) = \frac{H (n, k + 1)}{H (n, k)})$
とおく。
各 $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{aligned} 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{aligned}$
という関係を用いて回帰的に $R_{i + 1}$ を求めていくのも効果的である。
$I$ を十分大きく取り、未知の多項式 $p_{0} (n), \dots, p_{I} (n)$ に関する線形方程式
$\sum_{i = 0}^{I} p_{i} (n) R_{i} (n, k) = 0$
を解く。
このとき
$G (n, k) = (\sum_{i = 0}^{I} p_{i} (n) S_{i} (n, k)) H (n, k)$
とおくと
$\sum_{i = 0}^{I} p_{i} (n) F (n + i, k) = G (n, k + 1) - G (n, k)$
が成り立つ。

計算例

　では実際の計算例を見ていきましょう。

$f (n) = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k}$
を閉形式に表せ。

解説

$F (n, k) = (\binom{n}{k}) x^{k}$
の核と殻として
$K (k) = \frac{n - k}{k + 1} x, S (k) = 1 = \frac{k + 1}{k + 1}$
を取る。このとき
$K (k) - 1 = \frac{n + 1}{k + 1} x - (x + 1)$
に注意して
$\begin{aligned} S_{0} (k) & = - \frac{1}{x + 1} \\ S_{1} (k) & = - \frac{n + 1}{n - k + 1} \end{aligned}$
とおくと
$\begin{aligned} 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{aligned}$
と変形できる。
　したがって
$\begin{aligned} G (n, k) & = (S_{1} (k) - (x + 1) S_{0} (k)) F (n, k) \\ = - (\binom{n}{k - 1}) x^{k} \end{aligned}$
とおくと
$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_{k = 0}^{n} {(\binom{n}{k})}^{2}$
を閉形式に表せ。

解説

$F (n, k) = {(\binom{n}{k})}^{2}$
の核と殻として
$\begin{aligned} 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{aligned}$
を取る。このとき
$\begin{aligned} 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} - (2 n + 1) \end{aligned}$
が成り立つことに注意し
$\begin{aligned} S_{0} (k) & = - \frac{1}{2 n + 1} (k + \frac{n + 1}{2}) \\ S_{1} (k) & = - \frac{(n + 1)^{2}}{(n - k + 1)^{2}} \end{aligned}$
とおくと
$\begin{aligned} S (k) & = K (k) S_{0} (k + 1) - S_{0} (k) + \frac{n + 1}{2 (2 n + 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{aligned}$
と変形できる。
　したがって
$\begin{aligned} G (n, k) & = ((n + 1) S_{1} (k) - 2 (2 n + 1) S_{0} (k)) F (n, k) \\ = - (3 n - 2 k + 3) {(\binom{n}{k - 1})}^{2} \end{aligned}$
とおくと
$(n + 1) F (n + 1, k) - 2 (2 n + 1) F (n, k) = G (n, k + 1) - G (n, k)$
が成り立ち、これを $k$ について足し合わせることで
$f (n) = \sum_{k = 0}^{n} {(\binom{n}{k})}^{2}$
についての漸化式
$(n + 1) f (n + 1) - 2 (2 n + 1) f (n) = 0$
が得られる。また $f (0)$ に注意すると
$f (n) = \frac{2 n (2 n - 1)}{n^{2}} f (n - 1) = \frac{(2 n)!}{(n!)^{2}} f (0) = (\binom{2 n}{n})$
を求まる。

　 Zeilberger's algorithm による解法だと
$(\begin{matrix} 1 & 0 & 0 & 2 n + 1 \\ 2 & 0 & - 2 & n - 1 \\ 1 & 1 & - 1 & - 1 \end{matrix}) (\begin{matrix} A_{0} \\ A_{1} \\ B_{0} \\ B_{1} \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix})$
という煩雑な線形方程式を導出および求解しなければなりませんでしたが、今回の記事における手法ではこのように
$(p_{1} (n) + p_{0} (n) \frac{n + 1}{2 (2 n + 1)}) \frac{(n + 1)^{2}}{(k + 1)^{2}} = 0$
という( $p_{0} (n), p_{1} (n)$ についての)簡単な方程式に帰着でき、計算が非常に楽であることが実感できますね。

$f (n) = \sum_{k = 0}^{n} {(\binom{n}{k})}^{3}$
の満たす漸化式を求めよ。

解説

$F (n, k) = {(\binom{n}{k})}^{3}$
の核と殻として
$\begin{aligned} 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{aligned}$
を取る。このとき
$\begin{aligned} S_{0} (k) & = - \frac{1}{2} \\ 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{aligned}$
とおくと
$\begin{aligned} S (k) & = K (k) S_{0} (k + 1) - S_{0} (k) + \frac{1}{2} (\frac{(n + 1)^{3}}{(k + 1)^{3}} - \frac{3 (n + 1)^{2}}{(k + 1)^{2}} + \frac{3 (n + 1)}{k + 1}) \\ \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}} (\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}}) \\ = K (k) S_{2}^{'} (k + 1) - S_{2}^{'} (k) \\ + \frac{(n + 1)^{3}}{(n + 2)^{2}} (\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}}) \\ = K (k) S_{2}^{'} (k + 1) - S_{2}^{'} (k) + \frac{(n + 1)^{3}}{(n + 2)^{2}} (\frac{11 n^{2} + 29 n + 20}{(k + 1)^{3}} - \frac{12 (n + 1)}{(k + 1)^{2}} + \frac{12}{k + 1}) \end{aligned}$
が成り立つので $p_{0} (n), p_{1} (n), p_{2} (n)$ についての方程式
$\begin{aligned} 0 = & p_{2} (n) \frac{(n + 1)^{3}}{(n + 2)^{2}} (\frac{11 n^{2} + 29 n + 20}{(k + 1)^{3}} - \frac{12 (n + 1)}{(k + 1)^{2}} + \frac{12}{k + 1}) \\ + p_{1} (n) \frac{(n + 1)^{3}}{(k + 1)^{3}} \\ + p_{0} (n) \frac{1}{2} (\frac{(n + 1)^{3}}{(k + 1)^{3}} - \frac{3 (n + 1)^{2}}{(k + 1)^{2}} + \frac{3 (n + 1)}{k + 1}) \end{aligned}$
を解くことで
$(n + 2)^{2} f (n + 2) - (7 n^{2} + 21 n + 16) f (n + 1) - 8 (n + 1)^{2} f (n) = 0$
という漸化式が得られる。