インテジャーズ

インテジャーズ

数、特に整数に関する記事。

奇跡の漸化式〜creative telescoping〜

定理解説

この記事では、Apéryの定理の証明においてクリティカルな部分となる次の定理を証明します：

定理 (Cohen-Zagier) 漸化式
(n+1)^3a_{n+1}-(34n^3+51n^2+27n+5)a_n+n^3a_{n-1}=0
で定まる二つの数列\{u_n\}, \ \{v_n\}を考える：
\begin{align}&u_0=1, u_1=5, u_n=a_n \ (n \geq 2), \\ &v_0=0, v_1=6, v_n=a_n\ (n \geq 2).\end{align}

このとき、\{u_n\}, \ \{v_n\}の一般項は

\displaystyle u_n = \sum_{k=0}^n\binom{n}{k}^2\binom{n+k}{k}^2,\ v_n = \sum_{k=0}^n\binom{n}{k}^2\binom{n+k}{k}^2u_{k, n},
\displaystyle u_{k, n} := \sum_{m=1}^n\frac{1}{m^3}+\sum_{m=1}^k\frac{(-1)^{m-1}}{2m^3\binom{n}{m}\binom{n+m}{m}}
で与えられる。

パスカルの三角形に現れない二項係数については\displaystyle \binom{0}{0}=1, \ \binom{n}{k} = 0 \ (n < k)と規定します。

証明のテクニックは「望遠鏡和を作る(creative telescoping)」です*1。
integers.hatenablog.com
Apéryの証明は完全に初等的であるため、高等な道具・武器を一切使いません。全てを望遠鏡和に頼るのです。ちなみに、他の文献では計算が省略されている部分のため、計算していて楽(苦)しかったです。でも、自分で計算して初めて「確かに証明されている」という強固な確信が得られました。


\displaystyle b_{k, n} :=\binom{n}{k}^2\binom{n+k}{k}^2=\frac{(n+k)!^2}{k!^4(n-k)!^2}

と省略記号を導入すると、\{u_n\}の場合に示すべきことは

\displaystyle (n+1)^3\sum_{k=0}^{n+1}b_{k, n+1}- (34n^3+51n^2+27n+5)\sum_{k=0}^nb_{k, n}+n^3\sum_{k=0}^{n-1}b_{k, n-1}=0

すなわち、

\displaystyle \sum_{k=0}^n\left\{ (n+1)^3b_{k, n+1}-(34n^3+51n^2+27n+5)b_{k, n}+n^3b_{k, n-1}\right\} +(n+1)^3b_{n+1, n+1}=0

です。B_{k, n}を

\displaystyle B_{k, n} := 4(2n+1)\left\{ k(2k+1)-(2n+1)^2\right\} \binom{n}{k}^2\binom{n+k}{k}^2

と定義しましょう。このとき、

主張１
\displaystyle (n+1)^3b_{k, n+1}-(34n^3+51n^2+27n+5)b_{k, n}+n^3b_{k, n-1} = B_{k, n}-B_{k-1, n}

が成り立つことを示せばよいです。

実際、

\displaystyle B_{n, n}=4(2n+1)\left\{ n(2n+1)-(2n+1)^2\right\} \binom{2n}{n}^2 = -4(n+1)(2n+1)^2\binom{2n}{n}^2

かつ

\displaystyle \binom{2n+2}{n+1} = \frac{2(2n+1)}{n+1}\binom{2n}{n}

より

\displaystyle B_{n, n} = -(n+1)^3b_{n+1, n+1}

が成り立つので、主張１より

\begin{align} &\sum_{k=0}^n\left\{ (n+1)^3b_{k, n+1} -(34n^3+51n^2+27n+5)b_{k, n}+n^3b_{k, n-1}\right\} +(n+1)^3b_{n+1, n+1} \\ &=\sum_{k=0}^n (B_{k, n}-B_{k-1, n}) + (n+1)^3b_{n+1, n+1} \\ &= B_{n, n}-B_{-1, n}+ (n+1)^3b_{n+1, n+1} = 0 \end{align}


が示されます(望遠鏡和およびB_{-1, n}=0)。

主張１は直接計算で確かめられる状況になっていて、

\begin{align}(\text{左辺})\times \frac{k!^4(n-k+1)!^2}{(n+k-1)!^2} &= (n+1)^3(n+k)^2(n+k+1)^2\\ & \ \ \ \ -(34n^3+51n^2+27n+5)(n-k+1)^2(n+k)^2 \\ & \ \ \ \ +n^3(n-k)^2(n-k+1)^2 \\ &= −4k^2+12k^3−4k^4−8kn−8k^2n+64k^3n−24k^4n\\ & \ \ \ \ −4n^2−52kn^2+40k^2n^2+120k^3n^2−48k^4n^2\\ & \ \ \ \ −32n^3−128kn^3+160k^2n^3+80k^3n^3−32k^4n^3\\ & \ \ \ \ −100n^4−140kn^4+200k^2n^4\\ & \ \ \ \ −152n^5−56kn^5+80k^2n^5 \\ & \ \ \ \ −112n^6−32n^7\end{align}

および

\begin{align}(\text{右辺})\times \frac{k!^4(n-k+1)!^2}{(n+k-1)!^2} &= 4(2n+1)\left\{ k(2n+1)-(2n+1)^2\right\} (n-k+1)^2(n+k)^2 \\ & \ \ \ \ -4(2n+1)\left\{ (k-1)(2k-1) - (2n+1)^2\right\} k^4 \\ &= −4k^2+12k^3−4k^4−8kn−8k^2n+64k^3n−24k^4n\\ & \ \ \ \ −4n^2−52kn^2+40k^2n^2+120k^3n^2−48k^4n^2\\ & \ \ \ \ −32n^3−128kn^3+160k^2n^3+80k^3n^3−32k^4n^3\\ & \ \ \ \ −100n^4−140kn^4+200k^2n^4\\ & \ \ \ \ −152n^5−56kn^5+80k^2n^5 \\ & \ \ \ \ −112n^6−32n^7\end{align}

から主張１が正しいことが分かります。以上で\{u_n\}の場合が示されました*2。



次に、\{v_n\}の場合に示しましょう。示すべきことは

\displaystyle {\small (n+1)^3\sum_{k=0}^{n+1}b_{k, n+1}u_{k, n+1}- (34n^3+51n^2+27n+5)\sum_{k=0}^nb_{k, n}u_{k, n}+n^3\sum_{k=0}^{n-1}b_{k, n-1}u_{k, n-1}=0}

すなわち、

\begin{align} \sum_{k=0}^n&\left\{ (n+1)^3b_{k, n+1}u_{k, n+1}-(34n^3+51n^2+27n+5)b_{k, n}u_{k, n}+n^3b_{k, n-1}u_{k, n-1}\right\} \\ &+(n+1)^3b_{n+1, n+1}u_{n+1, n+1}=0\end{align}

です。A_{k, n}を

\displaystyle A_{k, n}:=B_{k, n}u_{k, n}+\frac{5(2n+1)(-1)^{k-1}k}{n(n+1)}\binom{n}{k}\binom{n+k}{k}

と定義します。このとき、

主張２
{\small (n+1)^3b_{k, n+1}u_{k, n+1}-(34n^3+51n^2+27n+5)b_{k, n}u_{k, n}+n^3b_{k, n-1}u_{k, n-1}= A_{k, n}-A_{k-1, n}}

が成り立つことを示せばよいです。

実際、

integers.hatenablog.com

の「Apéryはどのようにして近似列を見つけたのか？」の節で示したように

\displaystyle u_{n, n}=\frac{5}{2}\sum_{m=1}^n\frac{(-1)^{m-1}}{m^3\binom{2m}{m}}

に注意すると、

\begin{align} A_{n, n} &= B_{n, n}u_{n, n}+\frac{5(2n+1)(-1)^{n-1}}{n+1}\binom{2n}{n} \\ &= -(n+1)^3b_{n+1, n+1}\frac{5}{2}\sum_{m=1}^n\frac{(-1)^{m-1}}{m^3\binom{2m}{m}} - (n+1)^3b_{n+1, n+1}\cdot \frac{5}{2}\cdot \frac{(-1)^n}{(n+1)^3\binom{2n+2}{n+1}} \\ &= -(n+1)^3b_{n+1, n+1}u_{n+1, n+1}\end{align}

が成り立つので、主張２より

\begin{align} &\sum_{k=0}^n\left\{ (n+1)^3b_{k, n+1}u_{k, n+1} -(34n^3+51n^2+27n+5)b_{k, n}u_{k, n} +n^3b_{k, n-1}u_{k, n-1}\right\}\\ & \ \ \ \ +(n+1)^3b_{n+1, n+1}u_{n+1, n+1} \\ &=\sum_{k=0}^n (A_{k, n}-A_{k-1, n}) + (n+1)^3b_{n+1, n+1}u_{n+1, n+1} \\ &= A_{n, n}-A_{-1, n}+ (n+1)^3b_{n+1, n+1}u_{n+1, n+1} = 0 \end{align}


が示されます(望遠鏡和およびA_{-1, n}=0)。

最後に主張２を示しましょう。主張１より

\begin{align}&(n+1)^3b_{k, n+1}u_{k, n+1}-(34n^3+51n^2+27n+5)b_{k, n}u_{k, n}+n^3b_{k, n-1}u_{k, n-1}\\ &= (B_{k, n}-B_{k-1, n})u_{k, n}+(n+1)^3b_{k, n+1}(u_{k, n+1}-u_{k,n}) - n^3b_{k, n-1}(u_{k, n}-u_{k, n-1}) \\ &= B_{k, n}u_{k, n}-B_{k-1, n}u_{k-1, n} + B_{k-1, n}(u_{k-1, n}-u_{k, n}) \\ &\ \ \ + (n+1)^3b_{k, n+1}(u_{k, n+1}-u_{k,n}) - n^3b_{k, n-1}(u_{k, n}-u_{k, n-1})\end{align}

と変形できます。よって、次の二つの材料があれば計算ができることが分かります：

材料１ \ \displaystyle u_{k, n}-u_{k, n-1} = (-1)^k\frac{k!^2(n-k-1)!}{n^2(n+k)!}.

証明. これもcreative telescopingによって証明します。

\begin{align}&\frac{(-1)^{m-1}}{2m^3\binom{n}{m}\binom{n+m}{m}}-\frac{(-1)^{m-1}}{2m^3\binom{n-1}{m}\binom{n-1+m}{m}} \\ &= \frac{(-1)^{m-1}(m-1)!^2(n-m)!}{2m(n+m)!}-\frac{(-1)^{m-1}(m-1)!^2(n-1-m)!}{2m(n-1+m)!} \\ &= \frac{(-1)^{m-1}(m-1)!^2(n-1-m)!\{(n-m)-(n+m)\}}{2m(n+m)!} \\ &= \frac{(-1)^m(m-1)!^2(n-m-1)!}{(n+m)!}\end{align}

なので、

\displaystyle u_{k, n}-u_{k, n-1} = \frac{1}{n^3}+\sum_{m=1}^k\frac{(-1)^m(m-1)!^2(n-m-1)!}{(n+m)!}.

ここで、次のように望遠鏡和の形を作ることができる：

\begin{align}&\frac{(-1)^mm!^2(n-m-1)!}{n^2(n+m)!} - \frac{(-1)^{m-1}(m-1)!^2(n-m)!}{n^2(n+m-1)!} \\ &= \frac{(-1)^m(m-1)!^2(n-m-1)!}{n^2(n+m)!}\{m^2+(n-m)(n+m)\} \\ &= \frac{(-1)^m(m-1)!^2(n-m-1)!}{(n+m)!}.\end{align}

従って、

\begin{align}u_{k,n}-u_{k, n-1} &= \frac{1}{n^3}+\sum_{m=1}^k \left( \frac{(-1)^mm!^2(n-m-1)!}{n^2(n+m)!} - \frac{(-1)^{m-1}(m-1)!^2(n-m)!}{n^2(n+m-1)!} \right) \\ &= (-1)^k\frac{k!^2(n-k-1)!}{n^2(n+k)!}\end{align}

を得る。 Q.E.D.

材料２ \ \displaystyle u_{k, n}-u_{k-1, n} = \frac{(-1)^{k-1}}{2k^3\binom{n}{k}\binom{n+k}{k}}.

証明. こちらは定義から即座に分かる。 Q.E.D.

示すべき等式は

\begin{align}&B_{k-1, n}(u_{k-1, n}-u_{k, n})+(n+1)^3b_{k, n+1}(u_{k, n+1}-u_{k, n})-n^3b_{k, n-1}(u_{k, n}-u_{k, n-1}) \\ &= \frac{5(2n+1)(-1)^{k-1}k}{n(n+1)}\binom{n}{k}\binom{n+k}{k} - \frac{5(2n+1)(-1)^k(k-1)}{n(n+1)}\binom{n}{k-1}\binom{n+k-1}{k-1} \end{align}

です(①とします)。

材料２より、

\begin{align} &B_{k-1, n}(u_{k-1, n}-u_{k, n}) \\ &= 4(2n+1)\left\{ (k-1)(2k-1)-(2n+1)^2\right\}\binom{n}{k-1}^2\binom{n+k-1}{k-1}^2\cdot \frac{(-1)^k}{2k^3\binom{n}{k}\binom{n+k}{k}} \\ &= (-1)^k2(2n+1)\left\{(k-1)(2k-1)-(2n+1)^2\right\}\frac{(n+k-1)!}{k(k-1)!^2(n-k+1)!(n-k+1)(n+k)}\end{align}

であり、材料１より

\displaystyle (n+1)^3b_{k, n+1}(u_{k, n+1}-u_{k, n}) = (-1)^k(n+1)\frac{(n+k+1)!}{k!^2(n+1-k)!(n+1-k)},

\displaystyle n^3b_{k, n-1} (u_{k, n}-u_{k, n-1}) = (-1)^kn\frac{(n+k-1)!}{k!^2(n+k)(n-1-k)!}

を得ます。よって、

\displaystyle C_{k, n} := (-1)^k\frac{k!^2(n-k+1)!(n+1-k)(n+k)}{(n+k-1)!}

とすると

\begin{align} \text{①の左辺} \times C_{k, n} = \ &2(2n+1)\left\{ (k-1)(2k-1)-(2n+1)^2\right\} k \\ &+(n+1)(n+k)^2(n+k+1) \\ &-n(n-k)(n-k+1)(n+1-k)\end{align}

と計算されます。

\begin{align} &(n+1)(n+k)^2(n+k+1)-n(n-k)(n-k+1)(n+1-k) \\ &= 2k^3n+k^3+2k^2n+k^2+6kn^3+9kn^2+3kn\\ &= k(2n+1)(k^2+k+3n^2+3n)\end{align}

に注意すれば、

\displaystyle \text{①の左辺} \times C_{k, n} = 5k(2n+1)(k^2-k-n^2-n) ー②.

一方、

\begin{align}\text{①の右辺}&= (-1)^{k-1}\frac{5(2n+1)}{n(n+1)}\left\{ \frac{k(n+k)!}{k!^2(n-k)!}+\frac{(k-1)(n+k-1)!}{(k-1)!^2(n-k+1)!} \right\} \\ &= (-1)^{k-1}5(2n+1)\frac{(n+k-1)!}{k!(k-1)!(n-k+1)!}\end{align}

より

\begin{align} \text{①の右辺} \times C_{k, n} &= -5k(2n+1)(n+1-k)(n+k)\\ &= 5k(2n+1)(k^2-k-n^2-n)\end{align}

と計算できるので、②と比較して、①が証明されました。すなわち、主張２が示され、冒頭で掲げた定理の証明が完了します。


大変でした。この大変さを経験すると、Beukersによる別証明がいかにエレガントか実感できます。

*1:とりあえずApéryの定理の証明が正しいことを確認することに重きを置いているため、望遠鏡和を作る部分については天下り的に書いています(どうやって思いつくかについては言及しないということ)。しかしながら、自分で証明を思いつく必要のある立場に立つと、このB_{k, n}を見つけることが最も難しい部分です。この記事ではZeilberger's Algorithmについては記述しません。

*2:Wikipediaの「アペリーの定理」には「アペリーの証明は、一箇所手計算ではできないところが含まれているといわれており、」とありますが、コンピュータなしに証明が正しいかをチェックできないという話ではありません。四色定理の証明におけるコンピュータ使用レベルの話ではないです。B_{k, n}を見つけたり、最後の多項式の展開を実行するときなどにコンピュータを使った方が速いのは確かです。