超幾何数列の基礎10：手計算のすゝめ
はじめに
この記事では
これまでの記事
に引き続き超幾何数列の基本事項についてまとめていきます。
さて
第二回の記事
では次のような問題
与えられた超幾何数列$H(n)$に対し
$$H(n)=T(n+1)-T(n)$$
を満たすような超幾何数列$T(n)$はどのように求められるか。また求まらない場合はどのように判定できるか。
を機械的に解決する方法としてGosper's algorithmというものを紹介しました。
ただその記事における説明ではやや形式的および天下り的なところがあったため、本質的に何が起こっているのかがわかりづらかったり、それ故に手順が覚えづらかったりと手計算で実行するにはやや難がありました(実際私も扱いづらさを感じていました)。
また
その後の記事
にて紹介したAbramov-Petkovšek reductionという手法もGosper's algorithmの補助としてかなり有用であるのに対し、やはり手順がわかりづらいという難点がありました。
なので今回と次回の記事ではそれらの手法をより手計算で実行しやすくできるよう、私なりに考えてみたことについて紹介していこうと思います。
掃き出し法
今回の記事ではまずGosper's algorithmを掃き出し法(仮)という考え方を用いて説明し直していこうと思います。
掃き出し法とは大雑把に言うと、$H(n)$を適当に
$$H(n)=(d\ \mbox{次多項式})\times(\mbox{難しい関数})$$
と分解したとき、この多項式の次数の高い項を掃き出す、つまり
\begin{align}
H(n)={}&(d\ \mbox{次未満の多項式})\times(\mbox{難しい関数})\\
&\quad+T'(n+1)-T'(n)
\end{align}
と変形できるような$T'(n)$を見つけることで次数を下げていこうという手法となっています。
概説
例えば
$$H(n)=\frac{(\frac12)_n}{n!}\frac{8n^2-26n+3}{3^n}$$
という数列を考えてみましょう。見ての通りこれは
$$H(n)=(8n^2-26n+3)\times\frac{(\frac12)_n}{3^nn!}$$
と分けて考えると良さそうだということが何となくわかると思います。
となるとまずは$8n^2$の項を掃き出すために
$$(2\ \mbox{次多項式})\times\frac{(\frac12)_n}{3^nn!}=T'(n+1)-T'(n)$$
という形の関係式を見つける必要がありますが、そのようなものは次の恒等式を用いることで量産することができます。
任意の数列$f(n)$に対し
$$f(n+1)\frac{(\frac12)_{n+1}}{3^nn!}-f(n)\frac{(\frac12)_n}{3^{n-1}(n-1)!}
=((n+\tfrac12)f(n+1)-3nf(n))\frac{(\frac12)_n}{3^nn!}$$
が成り立つ。
いまこの$f(n)=2n$の場合と、ついでに$f(n)=2$の場合を考えると
\begin{align}
(-4n^2+3n+1)\frac{(\frac12)_n}{3^nn!}
&=2(n+1)\frac{(\frac12)_{n+1}}{3^nn!}-2n\frac{(\frac12)_n}{3^{n-1}(n-1)!}\\
(-4n+1)\frac{(\frac12)_n}{3^nn!}
&=2\frac{(\frac12)_{n+1}}{3^nn!}-2\frac{(\frac12)_n}{3^{n-1}(n-1)!}
\end{align}
が成り立つことがわかります。
これがわかれば後は単純で、まず第一式を用いて$8n^2$の項を掃き出すと
\begin{align}
H(n)
={}&(8n^2-26n+3)\frac{(\frac12)_n}{3^nn!}\\
={}&(-20n+5)\frac{(\frac12)_n}{3^nn!}\\
&\quad-4(n+1)\frac{(\frac12)_{n+1}}{3^nn!}+4n\frac{(\frac12)_n}{3^{n-1}(n-1)!}
\end{align}
と変形でき、次に第二式を用いて$-20n$の項を掃き出すと
\begin{align}
H(n)={}&10\frac{(\frac12)_{n+1}}{3^nn!}-10\frac{(\frac12)_n}{3^{n-1}(n-1)!}\\
&\quad-4(n+1)\frac{(\frac12)_{n+1}}{3^nn!}+4n\frac{(\frac12)_n}{3^{n-1}(n-1)!}
\end{align}
と掃き出し切れるので
$$T(n)=(-4n+10)\frac{(\frac12)_n}{3^{n-1}(n-1)!}$$
が求める超幾何数列となることがわかります。
掃き出せない場合
では
$$H(n)=1\times\frac{(\frac12)_n}{3^nn!}$$
の場合はどうでしょうか。このときはどのような多項式$f(n)$を持ってきても
$$(n+\tfrac12)f(n+1)-3nf(n)=1$$
は成り立たないため、この方法では$H(n)$はこれ以上掃き出せません。
そして実はこのことから$H(n)$がGosper総和不可能であることが言えるため、これに関してはもはやどうすることもできません。
解説
では一般の超幾何数列$H(n)$に対する計算法について簡単に解説していきましょう。
ステップ1
$H(n)$を多項式部分$c(n)$と分子分母$A(n),B(n)$に分けて
$$H(n)=c(n)\frac{A(n)}{B(n)}$$
と分解する。ここで$A(n),B(n)$はその階比
$$a(n)=\frac{A(n+1)}{A(n)},\quad b(n)=\frac{B(n+1)}{B(n)}$$
が多項式となるような超幾何数列とした。
具体例と注意
例えば上の
$$H(n)=\frac{(\frac12)_n}{n!}\frac{8n^2-22n+3}{3^n}$$
の場合で言うと
$$c(n)=8n^2-22n+3,\quad A(n)=(\tfrac12)_n,\quad B(n)=3^nn!$$
とおくとよい。
もちろん$c(n),A(n),B(n)$の取り方にはある種の任意性があります。
例えば
\begin{align}
H(n)
&=\frac{(3n+2)!}{(3n)!}\frac{(2n)!}{(n!)^2}\\
&=(3n+1)(3n+2)\frac{4^n(\frac12)_n}{n!}
\end{align}
に対しては
$$c(n)=(3n+1)(3n+2),\quad A(n)=4^n(\tfrac12)_n,\quad B(n)=n!$$
と置くのが最適だが
$$c(n)=(3n+1)(3n+2),\quad A(n)=(2n)!,\quad B(n)=(n!)^2$$
とか
\begin{align}
c(n)&=9\\
A(n)&=(\tfrac13)_{n+1}(\tfrac23)_{n+1}\cdot 4^n(\tfrac12)_n\\
B(n)&=(\tfrac13)_n(\tfrac23)_n\cdot n!
\end{align}
のような置き方をしてしまうと上手くいかない(上手くいくこともある)。
このように$H(n)$の表示の仕方によっては最適な$c(n),A(n),B(n)$の取り方を見落としてしまい、以降の計算がどうしても上手くいかなくなることがありますが、そんなときは$A(n),B(n)$の階比$a(n),b(n)$が次の性質
- 任意の非負整数$h$に対し$a(n)$と$b(n+h)$は互いに素である。
例えば上の例において
$$A(n)=(2n)!,\quad B(n)=(n!)^2$$
と置いていた場合は
$$a(n)=(2n+2)(2n+1),\quad b=(n+1)^2$$
より$a(n)$と$b(n+0)$は共通因子$n+1$を持っており、また
\begin{align}
A(n)&=(\tfrac13)_{n+1}(\tfrac23)_{n+1}\cdot 4^n(\tfrac12)_n\\
B(n)&=(\tfrac13)_n(\tfrac23)_n\cdot n!
\end{align}
と置いていた場合は
\begin{align}
a(n)&=(n+\tfrac43)(n+\tfrac53)\cdot 4(n+\tfrac12)\\
b(n)&=(n+\tfrac13)(n+\tfrac23)\cdot n
\end{align}
より$a(n)$と$b(n+1)$は共通因子$(n+\frac43)(n+\frac53)$を持っていることがわかる。
ステップ2
任意の数列$f(n)$に対し
$$f(n+1)\frac{A(n+1)}{B(n)}-f(n)\frac{A(n)}{B(n-1)}=(a(n)f(n+1)-b(n-1)f(n))\frac{A(n)}{B(n)}$$
が成り立つ。
上の公式において$f(n)$に色んな次数の多項式を入れる、例えば$f(n)=1,n,n^2,\ldots$とおいていくことで
\begin{align}
(\mbox{多項式})\times\frac{A(n)}{B(n)}&=T'(n+1)-T'(n)\\
\bigg(T'(n)&=f(n)\frac{A(n)}{B(n-1)}\bigg)
\end{align}
という形の関係式を量産する。
補足
個人的にこの公式こそがこの手法における最も重要な式であると考えています。
これは不定積分の計算において、例えば
$$(\mbox{多項式})\times(\mbox{指数関数とか三角関数とか})$$
という形の関数の不定積分を求める際、とりあえず積の微分公式
$$(f(t)g(t))'=f'(t)g(t)+f(t)g'(t)$$
(つまり部分積分)を利用して多項式部分の次数を下げていけば上手くいくように、超幾何数列$H(n)$の不定和分$T(n)$を求める際にとりあえずこれさえ覚えておけば何とかなる公式がこの差分公式
$$f(n+1)\frac{A(n+1)}{B(n)}-f(n)\frac{A(n)}{B(n-1)}
=(a(n)f(n+1)-b(n-1)f(n))\frac{A(n)}{B(n)}$$
であるという感覚があります。
ステップ3
ステップ2において求めた関係式を用いて$c(n)$の高次の項を掃き出していく。
最終的にはある多項式$f(n)$とそれ以上掃き出せない多項式$c'(n)$であって
$$H(n)=f(n+1)\frac{A(n+1)}{B(n)}-f(n)\frac{A(n)}{B(n-1)}+c'(n)\frac{A(n)}{B(n)}$$
を満たすものが得られ、このとき$c'(n)=0$であれば
$$T(n)=f(n)\frac{A(n)}{B(n-1)}$$
が求める超幾何数列であり、$c'(n)\neq0$であれば$H(n)$はGosper総和不可能である、ということになる。
総和可能性について
ここで重要なのは$c(n),A(n),B(n)$の取り方が適切であれば、つまりステップ1においても(折り畳みにて)注意したように$A(n),B(n)$の階比$a(n),b(n)$が
- 任意の非負整数$h$に対し$a(n)$と$b(n+h)$は互いに素である。
を満たしているとき「掃き出し切れない$\iff$Gosper総和不可能」が言える、つまり次の主張が成り立つことにあります。
$H(n)$がGosper総和可能であれば、ある多項式$f(n)$が存在して
$$T(n)=f(n)\frac{A(n)}{B(n-1)}$$
が成り立つ。
なおその証明については 第二回の記事 の定理4を参照してください。
$c(n),A(n),B(n)$の取り方が不適切な例
$$H(n)=(3n+2)\frac{(2n)!}{(n!)^2}=(3n+2)\frac{4^n(\frac12)_n}{n!}$$
はGosper総和可能であり、実際対応する$T(n)$は
$$T(n)=\frac{4^n(\frac12)_n}{(n-1)!}$$
と求まるが
$$c(n)=2n+3,\quad A(n)=(2n)!,\quad B(n)=(n!)^2$$
と置いていた場合、どのような多項式$f(n)\neq0$に対しても
\begin{align}
&f(n+1)\frac{(2n+2)!}{(n!)^2}-f(n)\frac{(2n)!}{((n-1)!)^2}\\
={}&((2n+2)(2n+1)f(n+1)-n^2f(n))\frac{(2n)!}{(n!)^2}\\
={}&(2\ \mbox{次以上の多項式})\frac{(2n)!}{(n!)^2}
\end{align}
となってしまうので$1$次多項式である$c(n)$を掃き出すことができない(この場合も一応$f(n)=1/n$とおくことで$T(n)$を得ることはできる)。
計算例
とまあ何やら小難しい話をしてしまいましたが、やはりこういったものは習うより慣れなので、後は以下の計算例でも解くなり眺めるなりして感覚を掴んでもらえればと思います。
なお負整数の階乗の逆数については
$$\frac1{(-1)!}=0\cdot\frac1{0!}=0$$
のように解釈することに注意しましょう。
$$\sum^{n-1}_{k=0}(3k^3+4k^2+12k+1)k!$$
を求めよ。
解説
\begin{alignat}{3}
(n+1)^2(n+1)!-{}&&n^2n!&=(n^3+2n^2+3n+1)n!\\
(n+1)(n+1)!-{}&&n\cdot n!&=(n^2+n+1)n!\\
(n+1)!-{}&&n!&=n\cdot n!
\end{alignat}
に注意して
\begin{align}
3n^3+4n^2+12n+1
={}&3(n^3+2n^2+3n+1)\\
&-2n^2+3n-2\\
={}&3(n^3+2n^2+3n+1)\\
&-2(n^2+n+1)\\
&+5n
\end{align}
と掃き出していくことで
\begin{align}
(3n^3+4n^2+12n+1)n!&=T(n+1)-T(n)\\
\big(T(n)&=(3n^2-2n+5)n!\big)
\end{align}
が成り立つことがわかる。したがって
\begin{align}
\sum^{n-1}_{k=0}(3k^3+4k^2+12k+1)k!
&=T(n)-T(0)\\
&=(3n^2-2n+5)n!-5
\end{align}
を得る。
$$\sum^{n-1}_{k=0}(8k^3-59k-14)\frac{(3k)!}{15^k(k!)^3}$$
を求めよ。
解説
\begin{align}
(n+1)\frac{\frac{(3n+3)!}{(n+1)!}}{15^n(n!)^2}-n\frac{\frac{(3n)!}{n!}}{15^{n-1}((n-1)!)^2}
&=3(4n^3+18n^2+11n+2)\frac{(3n)!}{15^n(n!)^3}\\
\frac{\frac{(3n+3)!}{(n+1)!}}{15^n(n!)^2}-\frac{\frac{(3n)!}{n!}}{15^{n-1}((n-1)!)^2}
&=3(4n^2+9n+2)\frac{(3n)!}{15^n(n!)^3}
\end{align}
および
\begin{align}
8n^3-59n-14
={}&2(4n^3+18n^2+11n+2)\\
&-9(4n^2+9n+2)
\end{align}
に注意すると
$$\sum^{n-1}_{k=0}(8n^3-59n-14)\frac{(3k)!}{15^k(k!)^3}
=\l(\frac23n-3\r)\frac{(3n)!}{15^{n-1}((n-1)!)^2n!}$$
を得る。
ちなみに掃き出し法は有限和を求めるだけでなく、以下のような無限和を求めるのにも応用することができます。
$$\sum^\infty_{n=0}\frac{7n^3-6n^2+5n-4}{n!}$$
を求めよ。
解説
\begin{align}
\frac{(n+1)^2}{n!}-\frac{n^2}{(n-1)!}&=-\frac{n^3-n^2-2n-1}{n!}\\
\frac{n+1}{n!}-\frac n{(n-1)!}&=-\frac{n^2-n-1}{n!}\\
\frac1{n!}-\frac1{(n-1)!}&=-\frac{n-1}{n!}
\end{align}
に注意して
\begin{align}
7n^3-6n^2+5n-4
={}&7(n^3-n^2-2n-1)\\
&+(n^2-n-1)\\
&+20(n-1)\\
&+24
\end{align}
と掃き出していくことで
\begin{align}
\frac{7n^3-6n^2+5n-4}{n!}&=T(n+1)-T(n)+\frac{24}{n!}\\
\bigg(T(n)&=-\frac{7n^2+n+20}{(n-1)!}\bigg)
\end{align}
が成り立つことがわかる。したがって
\begin{align}
\sum^\infty_{n=0}\frac{7n^3-6n^2+5n-4}{n!}
&=T(\infty)-T(0)+\sum^\infty_{n=0}\frac{24}{n!}\\
&=24e
\end{align}
を得る。
$$\sum^\infty_{n=0}(3n+2)^3\frac{(\frac13)_n}{2^nn!}$$
を求めよ。
解説
\begin{align}
(n+1)^2\frac{(\frac13)_{n+1}}{2^nn!}-n^2\frac{(\frac13)_n}{2^{n-1}(n-1)!}
&=-\frac{3n^3-7n^2-5n-1}3\frac{(\frac13)_n}{2^nn!}\\
(n+1)\frac{(\frac13)_{n+1}}{2^nn!}-n\frac{(\frac13)_n}{2^{n-1}(n-1)!}
&=-\frac{3n^2-4n-1}3\frac{(\frac13)_n}{2^nn!}\\
\frac{(\frac13)_{n+1}}{2^nn!}-\frac{(\frac13)_n}{2^{n-1}(n-1)!}
&=-\frac{3n-1}3\frac{(\frac13)_n}{2^nn!}
\end{align}
および
\begin{align}
(3n+2)^3
={}&27n^3+54n^2+36n+8\\
={}&9(3n^3-7n^2-5n-1)\\
&+39(3n^2-4n-1)\\
&+79(3n-1)\\
&+135
\end{align}
に注意すると
\begin{align}
\sum^\infty_{n=0}(3n+2)^3\frac{(\frac13)_n}{2^nn!}
&=135\sum^\infty_{n=0}\frac{(\frac13)_n}{2^nn!}\\
&=\frac{135}{\sqrt[3]{1-\frac12}}\\
&=135\sqrt[3]2
\end{align}
を得る。
この記事を高評価した人
この記事に送られたバッジ
投稿者
