機械的に級数を導出する方法について

Gosperのアルゴリズム,超幾何数列,級数

あいさつ

んちゃ！
今回は境界条件を用いて級数の別表現を求めるZOY⭐︎

参考文献

級数の間の等式を示す

目的

今回の記事では下記の問題を機械的に解くことが目的

数列$\{C(m,n)\}_{(m,n)\in\mathbb{N}^{2}},\{D(m,n)\}_{(m,n)\in\mathbb{N}^{2}}\subset\mathbb{C}$および単調増加な関数$f:\mathbb{Z}\rightarrow \mathbb{Z}\quad(f(0)=0)$に対して以下の級数を定める。この時、以下の級数を定める。
ただし、$C(m,n)$は既知とする。
\begin{eqnarray} \left\{ \begin{array}{l} C(m,n)-\lambda(n)C(m,n-1)=D(m+1,n)-D(m,n)\\ g(n)\coloneqq\sum_{f(n)\lt m}C(m,n) \end{array} \right. \end{eqnarray}
この時以下の漸化式を得るので
\begin{eqnarray} g(n)&=&\sum_{f(n)\lt m}C(m,n)\\ &=&\sum_{f(n-1)\lt m}C(m,n)-\sum_{f(n-1)\lt m\leq f(n)}C(m,n)\\ &=&\sum_{f(n-1)\lt m}\{\lambda(n)C(m,n-1)+D(m+1,n)-D(m,n)\}-\sum_{f(n-1)\lt m\leq f(n)}C(m,n)\\ &=&\lambda(n)g(n-1)-D(f(n-1)+1,n)-\sum_{f(n-1)\lt m\leq f(n)}C(m,n) \end{eqnarray}
最終的に以下の式を得る。
\begin{eqnarray} g(0)&=&\sum_{0\lt m}C(m,0)\\ &=&\sum_{0\leq n}\frac{D(f(n)+1,n+1)+\sum_{f(n)\lt m\leq f(n+1)}C(m,n+1)}{\prod_{k=1}^{n+1}\lambda(k)} \end{eqnarray}
今回はこの式を使って級数の別表現を機械的に求めることが主題。
還元すれば$C(m,n)$に合わせて適切な$\lambda(n)$を求め、さらに$D(m,n)$を機械的に求めることが主題。

Gosperのアルゴリズム

一変数Gosperのアルゴリズム

超幾何数列$\{s_{n}\}_{n\in\mathbb{Z}},\{t_{n}\}_{n\in\mathbb{Z}}\subset\mathbb{C}$また有理関数
$\lambda(n)\in\mathbb{C}(n)$が以下の関係式を満たすとする。
\begin{equation} s_{n+1}-\lambda(n)s_{n}=t_{n} \end{equation}
この時、以下の式が成り立つ事を証明せよ。

$\displaystyle \frac{s_{n}}{t_{n}}\in\mathbb{C}(n)$
$y(n)\coloneqq\frac{s_{n}}{t_{n}},R(n)\coloneqq\frac{t_{n+1}}{t_{n}}$とすると
\begin{equation} R(n)y(n+1)-\lambda(n)y(n)=1 \end{equation}
$R(n)\coloneqq\frac{F(n)}{E(n)},\lambda(n)\coloneqq\frac{H(n)}{G(n)},y(n)\coloneqq\frac{B(n)}{A(n)}$とすると以下の式を解くことで解を得る。
\begin{eqnarray} \left\{ \begin{array}{l} \exists J\in\mathbb{Z}\ s.t.\ D_{J}(n)\coloneqq\gcd(F(n-1)G(n-1),E(n+J+1)H(n+J+1))\\ P(n)\coloneqq\prod_{j\in\{Jの候補\}}D_{j}(n)D_{j}(n-1)\cdots D_{j}(n-j)\\ A(n)\coloneqq\frac{f(n)}{P(n)}\\ F(n)G(n)P(n)f(n+1)-E(n)H(n)P(n+1)f(n)=E(n)G(n)P(n)P(n+1) \end{array} \right. \end{eqnarray}

[1]以下の式より明らか。
\begin{eqnarray} \frac{t_{n}}{s_{n}}&=&\frac{s_{n+1}}{s_{n}}-\lambda(n)\in\mathbb{C}(n) \end{eqnarray}
[2]
\begin{eqnarray} \frac{s_{n+1}-\lambda(n)s_{n}}{t_{n}}&=&\frac{t_{n+1}}{t_{n}}\frac{s_{n+1}}{t_{n+1}}-\lambda(n)\frac{s_{n}}{t_{n}}\\ &=&R(n)y(n+1)-\lambda(n)y(n)\\ &=&1 \end{eqnarray}
[3]
\begin{equation} \frac{B(n+1)F(n)}{A(n+1)E(n)}-\frac{B(n)H(n)}{A(n)G(n)}=1 \end{equation}
より$n$に関する多項式を得る。
\begin{equation} A(n)B(n+1)F(n)G(n)-A(n+1)B(n)E(n)H(n)=A(n)A(n+1)E(n)G(n) \end{equation}
また次の様に変形できる。
\begin{equation} A(n)B(n+1)F(n)G(n)=A(n+1)E(n)\{A(n)G(n)+B(n)H(n)\} \end{equation}
次に$A(n)$の素因子$d(n)$を考えると
\begin{equation} d(n)|A(n+1)E(n)H(n) \end{equation}
故に以下の式を得る。
\begin{eqnarray} \left\{ \begin{array}{l} \exists J\in\mathbb{N}_{0}\ s.t.\ d(n),d(n-1),...,d(n-J)\mid A(n)\land d(n-J-1)\nmid A(n)\land d(n)\mid E(n+J+1)H(n+J+1) \end{array} \right. \end{eqnarray}
さらに$d(n+1)\mid A(n+1)\land d(n+1)\nmid A(n)$とすると、$d(n+1)\mid A(n)B(n+1)F(n)G(n)$なので
\begin{equation} d(n+1)\mid B(n+1)F(n)G(n) \end{equation}
なので$d(n)\mid F(n-1)G(n-1)$を得る。この条件より$J$を求める方法は下記の様になる。
\begin{eqnarray} \left\{ \begin{array}{l} d(n)|F(n-1)G(n-1)\\ d(n)|E(n+J+1)H(n+J+1)\\ \Res_{n}(F(n-1)G(n-1),E(n+J+1)H(n+J+1))=0 \end{array} \right. \end{eqnarray}
つまり、以下の手順で計算ができる。

$J=0$をまず代入し$\Res_{n}(F(n-1)G(n-1),E(n+1)H(n+1))=C\in\mathbb{Z}$を出す。
次に、$C$の約数$d_{1},d_{2},...,d_{K}$を出す。これを用いて$J=\pm d_{1},\pm d_{2},...,\pm d_{K}$を得る。
上記計算によって$\frac{A(n+1)}{A(n)}=\frac{p(n+1)}{p(n)}\frac{\tilde{A}(n+1)}{\tilde{A}(n)}\quad(\forall j\in\mathbb{N}: \gcd(\tilde{A}(n),\tilde{A}(n+j))=1)$の様に変形できる。
$D_{J}(n)\coloneqq\gcd(F(n-1)G(n-1),E(n+J+1)H(n+J+1))$の様に定めると
\begin{equation} d(n)d(n-1)\cdots d(n-J)\mid P(n)\coloneqq\prod_{j\in\{Jの候補\}}D_{j}(n)D_{j}(n-1)\cdots D_{j}(n-j) \end{equation}
であり$A(n)\mid P(n)$。故に$\exists \tilde{A}(n)\in\mathbb {C}[n]\ s.t.\ P(n)=\tilde{A}(n)A(n)$を得る。これから
\begin{eqnarray} y(n)&=&\frac{B(n)}{A(n)}\\ &=&\frac{\tilde{A}(n)B(n)}{\tilde{A}(n)A(n)}\\ &=&\frac{f(n)}{P(n)} \end{eqnarray}
整理して以下の多項式方程式を得る。
\begin{equation} F(n)G(n)P(n)f(n+1)-E(n)H(n)P(n+1)f(n)=E(n)G(n)P(n)P(n+1) \end{equation}

回答編

問題1に対してアルゴリズムを構成する。
$D(m,n)$を超幾何数列とする。この時以下の式を同時に満たす様にする事である。
\begin{equation} C(m,n)-\lambda(n)C(m,n-1)=D(m+1,n)-D(m,n) \end{equation}
つまり、

左辺:$C(m,n)$について単純な差分計算
右辺: $D(m,n)$はGosperのアルゴリズムを用いて計算

を適用する事で求めたい式を得る。
もう少し考える。
$C(m,n)$だけがわかっているとき$\lambda(n)$の調整により、解$D(m,n)$が存在する条件を求める。
[1]次のようにパラメータを決める。
\begin{eqnarray} \left\{ \begin{array}{l} M(m,n)\coloneqq\frac{C(m+1,n-1)}{C(m,n-1)}\coloneqq\frac{\beta(m,n)}{\alpha(m,n)}\\ N(m,n)\coloneqq\frac{C(m,n)}{C(m,n-1)}\coloneqq\frac{q(m,n)}{p(m,n)} \end{array} \right. \end{eqnarray}
すると$T(m,n)\coloneqq C(m,n)-\lambda(n)C(m,n-1)$とおけば以下の様に変形できる。
\begin{eqnarray} r(m,n)&\coloneqq&\frac{T(m+1,n)}{T(m,n)}\\ &=&\frac{C(m+1,n)-\lambda(n)C(m+1,n-1)}{C(m,n)-\lambda(n)C(m,n-1)}\\ &=&\frac{\frac{C(m+1,n-1)}{C(m,n-1)}\frac{C(m+1,n)}{C(m+1,n-1)}-\lambda(n)\frac{C(m+1,n-1)}{C(m,n-1)}}{\frac{C(m,n)}{C(m,n-1)}-\lambda(n)}\\ &=&M(m,n)\frac{N(m+1)-\lambda(n)}{N(m)-\lambda(n)}\\ &=&\frac{\beta(m,n)}{\alpha(m,n)}\frac{\frac{q(m+1,n)}{p(m+1,n)}-\lambda(n)}{\frac{q(m,n)}{p(m,n)}-\lambda(n)}\\ &=&\frac{\beta(m,n)p(m,n)}{\alpha(m,n)p(m+1,n)}\frac{q(m+1,n)-\lambda(n)p(m+1,n)}{q(m,n)-\lambda(n)p(m,n)} \end{eqnarray}
よって以下の記号を定め
\begin{eqnarray} \left\{ \begin{array}{l} a(m,n)\coloneqq \alpha(m,n)p(m+1,n)\\ b(m,n)\coloneqq \beta(m,n)p(m,n)\\ c(m,n)\coloneqq q(m,n)-\lambda(n)p(m,n) \end{array} \right. \end{eqnarray}
さらに必要なら、$\forall j\in\mathbb{N}: \gcd_{m}(a(m,n),b(m+j,n))=1$を満たす様に$Res_{m}(a(m,n),b(m+J,n))=0$を満たす$J$を求め$d(m,n)\mid a(m,n),b(m+J,n)$を求める事で調整する。
\begin{eqnarray} \left\{ \begin{array}{l} \displaystyle a(m,n)\coloneqq\tilde{a}(m,n)d(m,n)\\ \displaystyle b(m,n)\coloneqq\tilde{b}(m,n)d(m-J,n)\\ \displaystyle U(m,n)\coloneqq d(m,n)d(m+1,n)\cdots d(m+J-1,n)\\ \displaystyle\frac{b(m,n)}{a(m,n)}=\frac{\tilde{b}(m,n)}{\tilde{a}(m,n)}\frac{U(m+1,n)}{U(m,n)}\\ \tilde{c}(m,n)\coloneqq c(m,n)U(m,n) \end{array} \right. \end{eqnarray}
このような調整を繰り返して最終結果を
\begin{eqnarray} \left\{ \begin{array}{l} \displaystyle a(m,n)\coloneqq\tilde{a}(m,n)V_{a}(m,n)\\ \displaystyle b(m,n)\coloneqq\tilde{b}(m,n)V_{b}(m,n)\\ \displaystyle U(m,n)\coloneqq d(m,n)d(m+1,n)\cdots d(m+J-1,n)\\ \displaystyle\frac{b(m,n)}{a(m,n)}=\frac{\tilde{b}(m,n)}{\tilde{a}(m,n)}\frac{U_{c}(m+1,n)}{U_{c}(m,n)}\\ \tilde{c}(m,n)\coloneqq c(m,n)U_{c}(m,n) \end{array} \right. \end{eqnarray}
[0]そして$Y(m,n)\coloneqq\frac{D(m,n)}{T(m,n)}\coloneqq\frac{\tilde{a}(m-1,n)}{\tilde{c}(m,n)}X(m,n)$として以下の様に計算する。
\begin{equation} \tilde{b}(m,n)X(m+1,n)-\tilde{a}(m-1,n)V_{a}(m-1,n)X(m,n)=c(m,n)U_{c}(m,n) \end{equation}
ここで直接値を代入することで以下の式を得る。
\begin{equation} p(m,n)\{\beta(m,n)V_{a}(m-1,n)X(m+1,n)-\alpha(m-1,n)V_{b}(m,n)X(m,n)\}=\{q(m,n)-\lambda(n)p(m,n)\}U_{c}(m,n)V_{a}(m-1,n)V_{b}(m,n) \end{equation}
両辺$p(m,n)$で割り切れるので以下の式を得る。
\begin{equation} \beta(m,n)V_{a}(m-1,n)X(m+1,n)-\alpha(m-1,n)V_{b}(m,n)X(m,n)=\{q(m,n)-\lambda(n)p(m,n)\}\frac{U_{c}(m,n)V_{a}(m-1,n)V_{b}(m,n) }{p(m,n)}\end{equation}
よって以下の条件を満たす$\lambda(n)$を求める
[1]多項式: $\{q(m,n)-\lambda(n)p(m,n)\}\frac{U_{c}(m,n)V_{a}(m-1,n)V_{b}(m,n)}{p(m,n)}$なので$p(m,n)\mid U_{c}(m,n)V_{a}(m-1,n)V_{b}(m,n)$
[2]次数一致: $\max\{\deg{V_{a}}+\deg{\alpha}+\deg{X},\deg{V_{b}}+\deg{\beta}+\deg{X}\}=\deg\{q(m,n)+\lambda p(m,n)\}+\deg{U_{c}}+\deg{V_{a}}+\deg{V_{b}}-\deg{p(m,n)}$