望遠鏡の創作者に僕はなりたい

Gosper方程式,望遠鏡和,creatice telescoping

174

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

あいさつ

んちゃ！
今回の記事では皆で望遠鏡を作って遊ぶよ！
思い付き次第、随時更新するのだ！

望遠鏡和

超幾何数列

数列 $t (n)$ が超幾何数列であるとは、その階比 $\frac{t (n + 1)}{t (n)}$ がnに関する有理関数になるとき、 $t (n)$ を超幾何数列と呼ぶ。

望遠鏡和

$t (n), z (n)$ が超幾何数列で $t (n) = z (n + 1) - z (n)$ が成り立つとき、下記の式が成り立つ。
$\sum_{k = 0}^{n} t (n) = z (n + 1) - z (0)$

定理1の性質を満たす超幾何数列 $t (n), z (n)$ について $\frac{z (n)}{t (n)}$ は $n$ に関する有理関数になる。

$\frac{z (n)}{t (n)} = \frac{1}{\frac{z (n + 1)}{z (n)} - 1}$

定理により、ある $n$ に関する有理関数 $y (n)$ が存在して $z (n) = y (n) t (n)$ と書ける。また、超幾何数列の定義よりある有理関数 $r (n)$ を用いて $\frac{t (n + 1)}{t (n)} = r (n)$ とかけるので、次式が成り立つ。
$r (n) y (n + 1) - y (n) = 1$

これ何が嬉しいかって？
上記の有利関数 $y (n)$ を求めれば機械的に望遠鏡和を構成できるってことです。
ではさらに、進めてみよう。

次の性質を満たす $n$ に関する多項式 $a (n), b (n), c (n)$ が存在する。
$\frac{t (n + 1)}{t (n)} = \frac{a (n)}{b (n)} \frac{c (n + 1)}{c (n)} (\forall h \in {0} \cup N : gcd (a (n), b (n + h) = 1))$

[1]まず $t (n)$ は超幾何数列なのでその階比 $r (n) = \frac{t (n + 1)}{t (n)}$ は $n$ に関する有理関数。ゆえに互いに素な $n$ に関するある多項式 $f (n), g (n)$ を用いて
$r (n) = \frac{f (n)}{g (n)}$
次に、 $\exists h \in {0} \cup N s . t . gcd (f (n), g (n + h)) = u (n)$ を満たしたとすると、ある多項式 $\overset{―}{f} (n), \overset{―}{g} (n)$ が存在して次の様に書ける。
$\begin{array}{r} {\begin{cases} f (n) = \overset{―}{f} (n) u (n) \\ g (n) = \overset{―}{g (} (n) u (n - h) \end{cases} \end{array}$
これにより、以下の式を得る。
$\begin{array}{rcl} \frac{f (n)}{g (n)} & = & \frac{\overset{―}{f} (n)}{\overset{―}{g} (n)} \frac{u (n)}{u (n - h)} \\ = & \frac{\overset{―}{f} (n)}{\overset{―}{g} (n)} \frac{u (n - h + 1) u (n - h + 2) \dots u (n)}{u (n - h) u (n - h + 1) \dots u (n - 1)} \end{array}$
$U (n) = u (n - 1) u (n - 2) \dots u (n - h)$ と置くと次の式を得る。
$\frac{f (n)}{g (n)} = \frac{\overset{―}{f} (n)}{\overset{―}{g} (n)} \frac{U (n + 1)}{U (n)}$
上記操作を $G o s$ と名付ける。
[2]]よって、多項式 $\overset{―}{f} (n), \overset{―}{g} (n)$ についても同様に $G o s$ を行い、さらに繰り返せば、最終的に所要の多項式 $a (n), b (n), c (n)$ を得る。

Gosperの方程式

定理４の多項式 $a (n), b (n), c (n)$ が見つかっているとすると定理3の漸化式は別の有利関数x(n)を用いて $y (n) = \frac{b (n - 1)}{c (n)} x (n)$ と置くことで次の漸化式に書き直せる。
$a (n) x (n + 1) - b (n - 1) x (n) = c (n) (\forall h \in {0} \cup N : gcd (a (n), b (n + h)) = 1)$

任意の有限個の複素数 $c_{1}, c_{2}, . . ., c_{n} \in C$ に対して $c_{1} + 1, c_{2} + 1, . . ., c_{n} + 1 C$ を考えると、ある $i \in {1, 2, . . ., n}$ が存在して、任意の $j \in {1, 2, . . ., n}$ に対して以下の式が成り立つ。
$c_{i} + 1 \neq c j$

$c_{1}, c_{2}, . . ., c_{n}$ の実部を考え、それが最大値をとる $i \in {1, 2, . . ., n}$ を考えると任意の $j \in {1, 2, . . ., n}$ に対して $R e (c_{i} + 1) > R e (c_{j})$ が成り立つので $c_{i} + 1 \neq c_{j}$

定理5の漸化式の有理関数 $x (n)$ は存在するとすると、これは $n$ に関する多項式！

[1] $x (n)$ が $n$ に関する多項式でないとすると、ある互いに素な多項式 $f (n), g (n)$ が存在して $x (n) = \frac{f (n)}{g (n)}$ が成り立つ。ただし、 $g (n)$ は定数でない。
[2]元の与えられた漸化式は次の様に書き直せる。
$a (n) f (n + 1) g (n) - b (n - 1) f (n) g (n + 1) = c (n) g (n) g (n + 1)$
[3] $g (n)$ の規約因数(＊規約因数とは例えば $g (n) = (n + 1) (n + 2)$ の $n + 1$ や $n + 2$ の事)を考える。このとき補題6より適当な規約因数を考えると次の様にできることに注意する。
$u (n) | g (n) \land u (n + 1) ∤ g (n)$
また、非負整数 $h \in {0} \cup N$ で下記の式を満たすものの内最大のものを考える。
$u (n - h) | g (n) \land u (n - h) ∤ g (n + 1)$
すると[1],[2]より
$u (n + 1) | a (n) \land u (n - h) ∤ b (n - 1)$
すなち次の式が成り立つことを意味する。
$u (n + 1) | a (n), b (n + h)$
しかし、これは $a (n), b (n + h)$ が互いに素である事に反する。
ゆえに、 $g (n)$ は定数でなければならない。

イメージが湧かない人向け。
$g (n) = (n + 2) (n + 3)$ の場合 $g (n + 1) = (n + 3) (n + 4)$ であり $u (n) = n + 3, u (n + 1) = n + 4$ を選べばよく、また $h = 1$ として $u (n - 1)$ を用いれば
$\begin{array}{r} {\begin{cases} u (n) | g (n) \land u (n + 1) ∤ g (n) \\ u (n - 1) | g (n) \land u (n - 1) ∤ g (n + 1) \end{cases} \end{array}$

Gosper方程式の解法

$a (n) x (n + 1) - b (n - 1) x (n) = c (n) (\forall h \in {0} \cup N : gcd (a (n), b (n + h)) = 1)$
の解法について手短に考えてみる。
[1]定理7より、 $x (n)$ は $n$ に関する多項式となる事が分かっているのであらかじめ次数 $d$ の多項式として
$x (n) = \sum_{k = 0}^{d} C_{k} n^{k}$
という形を想定する。
[2] $x (n)$ の次数dに関する考察
1)左辺の最高次数の係数が打ち消しあわない場合：
この場合は簡単であり
$d + max {\deg a (n), \deg b (n)} = \deg c (n)$
より
$d = \deg c (n) - max {\deg a (n), \deg b (n)}$
2)最高次数の係数が打ち消しあう場合
下記の様に記号を定める。
$\begin{array}{r} {\begin{cases} a (n) = λ n^{N} + A n^{N - 1} + \dots \\ b (n) = λ n^{N} + B n - N - 1 + \dots \\ x (n) = C n^{d} + D n^{d - 1} + \dots \end{cases} \end{array}$
またGosper方程式は次の様に書き直せる。
$a (n) (x (n + 1) - x (n)) - (b (n - 1) - a (n)) x (n) = c (n)$
ゆえに最高次数に着目して計算すると $n^{d + N - 1}$ の係数は次の様に書ける事が分かる。
$λ (d C - D) - C (B - A)$
この係数が $0$ 出ない場合は次の様に書ける。
$d = \deg C (n) - N + 1$
またそうでない場合は
$d = \frac{B - A}{λ} + D$
を得る。
[3] $d < 0$ の場合は解が存在しない事を意味している。この場合はGosper総和不可能という。

作って遊ぼう

このままだと子葉氏のパクりみたいな記事になるので、少し趣向を変えてみる。
先の場合、先に超幾何数列 $t (n)$ を与えてから、Gosper方程式を導く手順について考えたけど、そうではなく、逆に $a (n), b (n)$ を先に与えて、多項式 $x (n)$ を動かす事で出来る望遠鏡和について考えてみよう。

$\begin{array}{r} {\begin{cases} a (n) = 1 \\ b (n) = 1 \end{cases} \end{array}$
の場合はもちろん $gcd (a (n), b (n + h)) = 1$ であるのでGosper方程式の条件も問題ない。
$x (n) = A n^{2} + B n + C$ であるとすると $c (n) = 2 A n + A + B$ ゆえに、
$\begin{array}{rcl} \frac{t (n + 1)}{t (n)} & = & \frac{2 A n + 3 A + B}{2 A n + A + B} \\ = & \frac{n + \frac{3 A + B}{2 A}}{n + \frac{A + B}{2 A}} \end{array}$
$t (n) = \frac{(\frac{3 A + B}{2 A})_{n}}{(\frac{A + B}{2 A})_{n}}$
$z (n) = \frac{A n^{2} + B n + C}{2 A n + A + B} \frac{(\frac{3 A + B}{2 A})_{n}}{(\frac{A + B}{2 A})_{n}}$
より
$\sum_{k = 0}^{n - 1} \frac{(\frac{3 A + B}{2 A})_{k}}{(\frac{A + B}{2 A})_{k}} = \frac{A n^{2} + B n + C}{2 A n + A + B} \frac{(\frac{3 A + B}{2 A})_{n}}{(\frac{A + B}{2 A})_{n}} - \frac{C}{A + B}$
特に $A = B = C = 1$ とすると
$\sum_{k = 0}^{n - 1} (k + 1) = \frac{n (n + 1)}{2}$

$\begin{array}{r} {\begin{cases} a (n) = 1 \\ b (n) = A n + B \end{cases} \end{array}$
と書ける場合ももちろん $gcd (a (n), b (n + h)) = 1$ を満たすのでGosper方程式の条件を満たしている。
$x (n) = K n + L$
とすると
$c (n) = - (K n + L) (A n - A + B - 1) + L$
$\frac{t (n + 1)}{t (n)} = \frac{1}{A n + B} \frac{(K n + K + L) (A n + B - 1) + L}{(K n + L) (A n - A + B - 1) + L}$
$t (n) = \prod_{k = 0}^{n} \frac{1}{A k + B - A} \frac{(K k + L) (A k - A + B - 1) + L}{(K k + L - K) (A k - 2 A + B - 1) + L}$
$z (n) = - \frac{(K n + L) (A n - A + B - 1) + L}{A n + B - A} (K n + L) \prod_{k = 0}^{n} \frac{1}{A k + B - A} \frac{(K k + L) (A k - A + B - 1) + L}{(K k + L - K) (A k - 2 A + B - 1) + L}$
以上より、
$\sum_{l = 0}^{\infty} \prod_{k = 0}^{l} \frac{1}{A k + B - A} \frac{(K k + L) (A k - A + B - 1) + L}{(K k + L) (A k - 2 A + B - 1) + L} = \frac{L^{3}}{(L - K) (B - 2 A - 1) + L}$

でもさー
上のGosperの方程式だけだと限界があるよね！
そこで次にSister Celineの方法を考えていくよ！

Sister Celines's method

まずは簡単な例で遊んでみよう！

次の数列 $f (n)$ の漸化式を求めよ！
$\begin{array}{rcl} f (n) & = & \sum_{k = 0}^{n} k (\begin{array}{c} n \\ k \end{array}) \\ = & \sum_{k = - \infty}^{\infty} k (\begin{array}{c} n \\ k \end{array}) \end{array}$

[1] $F (n, k) = k (\begin{matrix} n \\ k \end{matrix})$ とおく。そして次の様なP-再帰的式が成り立つと仮定してみる。
$a (n) F (n, k) + b (n) F (n + 1, k) + c (n) F (n, k + 1) + d (n) F (n + 1, k + 1) = 0$
注目すべきは、 $a, b, c, d$ は $n$ にのみに依存し、 $k$ に依存しない事。
[2]両辺を $F (n, k)$ で割ってみよう。すると次の様に書ける。
$a (n) + b (n) \frac{F (n + 1, k)}{F (n, k)} + c (n) \frac{F (n, k + 1)}{F (n, k)} + d (n) \frac{F (n + 1, k + 1)}{F (n, k)} = 0$
[3]次に $F (n, k) = k (\begin{matrix} n \\ k \end{matrix})$ を代入しよう。すると次式を得る。
$a + b \frac{n + 1}{n + 1 - k} + c \frac{n - k}{k} + d \frac{n + 1}{k} = 0$
より両辺に $k (n + 1 - k)$ をかけて整理すると次式を得る。
$(c - a) k^{2} + ((n + 1) a + (n + 1) b - (2 n + 1) c - n d) k + (n + 1) (c n + (n + 1) d) = 0$
[4][3]で得た最後の式は $k$ に依らず0でなければならないので、以下の連立方程式を得る。
$\begin{array}{r} {\begin{cases} c - a = 0 \\ (n + 1) a + (n + 1) b - (2 n + 1) c - n d = 0 \\ c n + (n + 1) d = 0 \end{cases} \end{array}$
よって、これを解くと
$\begin{array}{r} {\begin{cases} a = c = - \frac{n + 1}{n} d \\ b = 0 \\ c = - \frac{n + 1}{n} d \end{cases} \end{array}$
[5]
すなわち以下のP-再帰的な式を得る。
$- \frac{n + 1}{n} F (n, k) - \frac{n + 1}{n} F (n, k + 1) + F (n + 1, k + 1) = 0$
よって、両辺 $k$ について総和を取れば
$- \frac{n + 1}{n} f (n) - \frac{n + 1}{n} f (n) + f (n + 1) = - \frac{2 (n + 1)}{n} f (n) + f (n + 1) = 0$
[6]
上記の漸化式を解くと
$\begin{array}{rcl} f (n) & = & \frac{2 n}{n - 1} f (n - 1) \\ = & 2^{n - 1} n f (1) \\ = & 2^{n - 1} n \end{array}$