4

超幾何数列の基礎10:手計算のすゝめ

94
0

はじめに

 この記事では これまでの記事 に引き続き超幾何数列の基本事項についてまとめていきます。
 さて 第二回の記事 では次のような問題

 与えられた超幾何数列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 次多項式)×(難しい関数)
と分解したとき、この多項式の次数の高い項を掃き出す、つまり
H(n)=(d 次未満の多項式)×(難しい関数)+T(n+1)T(n)
と変形できるようなT(n)を見つけることで次数を下げていこうという手法となっています。

概説

 例えば
H(n)=(12)nn!8n226n+33n
という数列を考えてみましょう。見ての通りこれは
H(n)=(8n226n+3)×(12)n3nn!
と分けて考えると良さそうだということが何となくわかると思います。
 となるとまずは8n2の項を掃き出すために
(2 次多項式)×(12)n3nn!=T(n+1)T(n)
という形の関係式を見つける必要がありますが、そのようなものは次の恒等式を用いることで量産することができます。

 任意の数列f(n)に対し
f(n+1)(12)n+13nn!f(n)(12)n3n1(n1)!=((n+12)f(n+1)3nf(n))(12)n3nn!
が成り立つ。

 いまこのf(n)=2nの場合と、ついでにf(n)=2の場合を考えると
(4n2+3n+1)(12)n3nn!=2(n+1)(12)n+13nn!2n(12)n3n1(n1)!(4n+1)(12)n3nn!=2(12)n+13nn!2(12)n3n1(n1)!
が成り立つことがわかります。
 これがわかれば後は単純で、まず第一式を用いて8n2の項を掃き出すと
H(n)=(8n226n+3)(12)n3nn!=(20n+5)(12)n3nn!4(n+1)(12)n+13nn!+4n(12)n3n1(n1)!
と変形でき、次に第二式を用いて20nの項を掃き出すと
H(n)=10(12)n+13nn!10(12)n3n1(n1)!4(n+1)(12)n+13nn!+4n(12)n3n1(n1)!
と掃き出し切れるので
T(n)=(4n+10)(12)n3n1(n1)!
が求める超幾何数列となることがわかります。

掃き出せない場合

 では
H(n)=1×(12)n3nn!
の場合はどうでしょうか。このときはどのような多項式f(n)を持ってきても
(n+12)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)A(n)B(n)
と分解する。ここでA(n),B(n)はその階比
a(n)=A(n+1)A(n),b(n)=B(n+1)B(n)
が多項式となるような超幾何数列とした。

具体例と注意

 例えば上の
H(n)=(12)nn!8n222n+33n
の場合で言うと
c(n)=8n222n+3,A(n)=(12)n,B(n)=3nn!
とおくとよい。

 もちろんc(n),A(n),B(n)の取り方にはある種の任意性があります。

 例えば
H(n)=(3n+2)!(3n)!(2n)!(n!)2=(3n+1)(3n+2)4n(12)nn!
に対しては
c(n)=(3n+1)(3n+2),A(n)=4n(12)n,B(n)=n!
と置くのが最適だが
c(n)=(3n+1)(3n+2),A(n)=(2n)!,B(n)=(n!)2
とか
c(n)=9A(n)=(13)n+1(23)n+14n(12)nB(n)=(13)n(23)nn!
のような置き方をしてしまうと上手くいかない(上手くいくこともある)。

 このように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)!,B(n)=(n!)2
と置いていた場合は
a(n)=(2n+2)(2n+1),b=(n+1)2
よりa(n)b(n+0)は共通因子n+1を持っており、また
A(n)=(13)n+1(23)n+14n(12)nB(n)=(13)n(23)nn!
と置いていた場合は
a(n)=(n+43)(n+53)4(n+12)b(n)=(n+13)(n+23)n
よりa(n)b(n+1)は共通因子(n+43)(n+53)を持っていることがわかる。

ステップ2

 任意の数列f(n)に対し
f(n+1)A(n+1)B(n)f(n)A(n)B(n1)=(a(n)f(n+1)b(n1)f(n))A(n)B(n)
が成り立つ。

 上の公式においてf(n)に色んな次数の多項式を入れる、例えばf(n)=1,n,n2,とおいていくことで
(多項式)×A(n)B(n)=T(n+1)T(n)(T(n)=f(n)A(n)B(n1))
という形の関係式を量産する。

補足

 個人的にこの公式こそがこの手法における最も重要な式であると考えています。
 これは不定積分の計算において、例えば
(多項式)×(指数関数とか三角関数とか)
という形の関数の不定積分を求める際、とりあえず積の微分公式
(f(t)g(t))=f(t)g(t)+f(t)g(t)
(つまり部分積分)を利用して多項式部分の次数を下げていけば上手くいくように、超幾何数列H(n)の不定和分T(n)を求める際にとりあえずこれさえ覚えておけば何とかなる公式がこの差分公式
f(n+1)A(n+1)B(n)f(n)A(n)B(n1)=(a(n)f(n+1)b(n1)f(n))A(n)B(n)
であるという感覚があります。

ステップ3

 ステップ2において求めた関係式を用いてc(n)の高次の項を掃き出していく。
 最終的にはある多項式f(n)とそれ以上掃き出せない多項式c(n)であって
H(n)=f(n+1)A(n+1)B(n)f(n)A(n)B(n1)+c(n)A(n)B(n)
を満たすものが得られ、このときc(n)=0であれば
T(n)=f(n)A(n)B(n1)
が求める超幾何数列であり、c(n)0であればH(n)はGosper総和不可能である、ということになる。

総和可能性について

 ここで重要なのはc(n),A(n),B(n)の取り方が適切であれば、つまりステップ1においても(折り畳みにて)注意したようにA(n),B(n)の階比a(n),b(n)

  • 任意の非負整数hに対しa(n)b(n+h)は互いに素である。

を満たしているとき「掃き出し切れないGosper総和不可能」が言える、つまり次の主張が成り立つことにあります。

 H(n)がGosper総和可能であれば、ある多項式f(n)が存在して
T(n)=f(n)A(n)B(n1)
が成り立つ。

 なおその証明については 第二回の記事 の定理4を参照してください。

c(n),A(n),B(n)の取り方が不適切な例

H(n)=(3n+2)(2n)!(n!)2=(3n+2)4n(12)nn!
はGosper総和可能であり、実際対応するT(n)
T(n)=4n(12)n(n1)!
と求まるが
c(n)=2n+3,A(n)=(2n)!,B(n)=(n!)2
と置いていた場合、どのような多項式f(n)0に対しても
f(n+1)(2n+2)!(n!)2f(n)(2n)!((n1)!)2=((2n+2)(2n+1)f(n+1)n2f(n))(2n)!(n!)2=(2 次以上の多項式)(2n)!(n!)2
となってしまうので1次多項式であるc(n)を掃き出すことができない(この場合も一応f(n)=1/nとおくことでT(n)を得ることはできる)。

計算例

 とまあ何やら小難しい話をしてしまいましたが、やはりこういったものは習うより慣れなので、後は以下の計算例でも解くなり眺めるなりして感覚を掴んでもらえればと思います。
 なお負整数の階乗の逆数については
1(1)!=010!=0
のように解釈することに注意しましょう。

k=0n1(3k3+4k2+12k+1)k!
を求めよ。

解説

(n+1)2(n+1)!n2n!=(n3+2n2+3n+1)n!(n+1)(n+1)!nn!=(n2+n+1)n!(n+1)!n!=nn!
に注意して
3n3+4n2+12n+1=3(n3+2n2+3n+1)2n2+3n2=3(n3+2n2+3n+1)2(n2+n+1)+5n
と掃き出していくことで
(3n3+4n2+12n+1)n!=T(n+1)T(n)(T(n)=(3n22n+5)n!)
が成り立つことがわかる。したがって
k=0n1(3k3+4k2+12k+1)k!=T(n)T(0)=(3n22n+5)n!5
を得る。

k=0n1(8k359k14)(3k)!15k(k!)3
を求めよ。

解説

(n+1)(3n+3)!(n+1)!15n(n!)2n(3n)!n!15n1((n1)!)2=3(4n3+18n2+11n+2)(3n)!15n(n!)3(3n+3)!(n+1)!15n(n!)2(3n)!n!15n1((n1)!)2=3(4n2+9n+2)(3n)!15n(n!)3
および
8n359n14=2(4n3+18n2+11n+2)9(4n2+9n+2)
に注意すると
k=0n1(8n359n14)(3k)!15k(k!)3=(23n3)(3n)!15n1((n1)!)2n!
を得る。

 ちなみに掃き出し法は有限和を求めるだけでなく、以下のような無限和を求めるのにも応用することができます。

n=07n36n2+5n4n!
を求めよ。

解説

(n+1)2n!n2(n1)!=n3n22n1n!n+1n!n(n1)!=n2n1n!1n!1(n1)!=n1n!
に注意して
7n36n2+5n4=7(n3n22n1)+(n2n1)+20(n1)+24
と掃き出していくことで
7n36n2+5n4n!=T(n+1)T(n)+24n!(T(n)=7n2+n+20(n1)!)
が成り立つことがわかる。したがって
n=07n36n2+5n4n!=T()T(0)+n=024n!=24e
を得る。

n=0(3n+2)3(13)n2nn!
を求めよ。

解説

(n+1)2(13)n+12nn!n2(13)n2n1(n1)!=3n37n25n13(13)n2nn!(n+1)(13)n+12nn!n(13)n2n1(n1)!=3n24n13(13)n2nn!(13)n+12nn!(13)n2n1(n1)!=3n13(13)n2nn!
および
(3n+2)3=27n3+54n2+36n+8=9(3n37n25n1)+39(3n24n1)+79(3n1)+135
に注意すると
n=0(3n+2)3(13)n2nn!=135n=0(13)n2nn!=1351123=13523
を得る。

投稿日:33
更新日:33
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

子葉
子葉
1069
262486
主に複素解析、代数学、数論を学んでおります。 私の経験上、その証明が簡単に探しても見つからない、英語の文献を漁らないと載ってない、なんて定理の解説を主にやっていきます。 同じ経験をしている人の助けになれば。最近は自分用のノートになっている節があります。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 掃き出し法
  3. 概説
  4. 掃き出せない場合
  5. 解説
  6. ステップ1
  7. ステップ2
  8. ステップ3
  9. 総和可能性について
  10. 計算例