43：Göbel数列（エイプリルフール問題、問３の解説）

エイプリルフール記事君にこの問題が解けるか！？ - INTEGERSで出題した問３の解説を行います。

問題は次のようなものでした：

問３数列 $\{a_n\}_{n=1}^{\infty}$ を $a_1=1$ および

$na_{n+1}=1+a_1^2+a_2^2+\cdots +a_n^2$

によって定義する。
$a_1=1, \ a_2=2, \ a_3=3, \ a_4=5, \ a_5=10, \ a_6=28, \ a_7=154, \ a_8=3520, \dots$
このとき、任意の自然数 $n$ に対して $a_n$ が整数であることを証明せよ。

これはGöbel数列と呼ばれている数列で普通は $x_0=1$ ,

$\displaystyle x_{n+1} = \frac{1+x_0^2+x_1^2+\cdots +x_n^2}{n+1}$

で定義されるため、以降 $\{x_n\}$ を用いて解説します。

最初のいくつかの値を見てみると少し大きめの数が現れることが分かります：

$x_{0}= 1$
$x_{1}= 2$
$x_{2}= 3$
$x_{3}= 5$
$x_{4}= 10$
$x_{5}= 28$
$x_{6}= 154$
$x_{7}= 3520$
$x_{8}= 1551880$
$x_{9}= 267593772160$
$x_{10}= 7160642690122633501504$
$x_{11}= 4661345794146064133843098964919305264116096$

$\begin{equation}\begin{split}x_{12}= &1810678717716933442325741630275004084414865420898591223522682\\ &022447438928019172629856\end{split}\end{equation}$

$\begin{equation}\begin{split}x_{13}= &2521967245225414108125790971603617696902880162601604453290592\\ &8081411909054521468963035694105796668300270624304582308082917\\ &4307488383892818892448294858132739063481087616\end{split}\end{equation}$

$\begin{equation}\begin{split}x_{14}= &4543084847135617156827912757388745495368280304614840838595881\\ &8661849168624845686113232512374665144002986660355054429212523\\ &5174147640872384813465160305130148273242631727996782469247359\\ &0004311667893669816825659451437945264179017683087851534875769\\ &6125204303587647947798961480564408541809837455171811504569258\\ &94414444744263895766823050176\end{split}\end{equation}$

$\begin{equation}\begin{split}x_{15}= &1375974661884883593958307872179178705368405647167653708277552\\ &9680289124738126091022173768501691117657105157738355993025260\\ &1425024116126030171739982076897018413487680419215088685480135\\ &6030366186182424436442996889021994405615153205582903467344478\\ &7921231066181141022355650321865049688497263508855993365332059\\ &2235241033475869594100438984490724838465142948408287279920217\\ &4077593625353904681667598612880451668712691329300699545740348\\ &4379871141076455337522809690676805736112642146030785614549616\\ &2822829306418740752779770509108256234815385182670930999924522\\ &4806527712609283567103740647842272786590546895644500236443431\\ &510130695525780542823497682908835486798511724130649088896\end{split}\end{equation}$

しかし、確かに整数になっています。この問題のどこらへんがエイプリルフールかというと、 $x_{42}$ までは整数であるけれども、実は $x_{43}$ が整数ではないのです。

つまり、成り立たないものを証明せよと言っているので、どれだけ証明しようと努力しても証明できません。

更に質の悪いことに、数がとても大きくなっていくのでプログラムを組んで数列の値を実際に出力して整数でないことを示そうと思ってもそうそう簡単ではありません。

天下りではありますが、合同式を使って証明するのがよいです：

補題 $\ \ \ (n+1)x_{n+1}=x_n(x_n+n)$ が成立する。

証明. $n \geq 1$ のとき、

$(n+1)x_{n+1}=1+x_0^2+x_1^2+\cdots +x_{n-1}^2+x_n^2=nx_n+x_n^2=x_n(x_n+n)$

と計算できる。 Q.E.D.

命題 $\ \ x_{43} \not \in \mathbb{Z}.$

証明. 補題を使って逐次的に $\bmod{43}$ 計算を行う：

$x_6 \equiv 25, \ x_7 \equiv 37, \ \dots, \ x_{42} \equiv 33 \pmod{43}$

そうして

$43x_{43}=x_{42}(x_{42}+42)\equiv 33(33+42) = 2475 \equiv 24 \not \equiv 0 \pmod{43}$

であることから $x_{43} \not \in \mathbb{Z}$ がわかる。 Q.E.D.

$3$ -Göbel数列

$3$ -Göbel数列 $\{y_n\}$ は $y_0=1$ および

$\displaystyle y_{n+1}=\frac{1+y_0^3+y_1^3+\cdots +y_n^3}{n+1}$

によって定義されます。このとき、

$y_{0}= 1$
$y_{1}= 2$
$y_{2}= 5$
$y_{3}= 45$
$y_{4}= 22815$
$y_{5}= 2375152056927$
$y_{6}= 2233176271342403475345148513527359103$

$\begin{equation}\begin{split}y_{7}= &1591002909245851102188660218618116637818488622409702751192275\\ &216849119621798426607577261282879455499092734335\end{split}\end{equation}$

$\begin{equation}\begin{split}y_{8}= &5034112704245798738298258322579188433476515817956466946429212\\ &5321348158160494269116946265506555020806549020811668825458977\\ &3339597096425592058664300289453019603872547494341604380616942\\ &8406091398196863516063919549766986682160558163874313636469151\\ &4396231405780452828968277892968875196701042128377420495077899\\ &3750712646710773215\end{split}\end{equation}$

$\begin{equation}\begin{split}y_{9}= &1417510529593941229163479235889460904358029209430937165180487\\ &8075109688677066754239862080937922894104109566106688602909371\\ &7065791254272891571957698266943382187727272648019439861606841\\ &5365168345409156531272469369787020724219927792888859941586531\\ &8266041185090321318922889072299624613269784310714337125744372\\ &9524152817530517759276618211402439707845296514436982359897560\\ &3742918513365469074570063182737559885577377504500739130769457\\ &5418235438612494742910833355283052576052356196346388466588678\\ &6559687088369238285433690189566236145296733916233735809030446\\ &3975748625812092444313643276205895704703020154742718640803934\\ &4205146911599066337595012626372663648842452917921796528910990\\ &8489302192015667526403585806176551838389629118580869504542037\\ &1111821841409904822868055560380614991254586393151655752590322\\ &2506774172200989708650250130203622322858568744014655527646115\\ &8534862992849368003605983553169882270404743859389158697662275\\ &82759917655939988738946864442144554488094148868149655455\end{split}\end{equation}$

と最初の方の値は整数になっていますが、 $y_{89}$ に至って整数でない値をとります。

$k$ -Göbel数列

$k$ を $2$ 以上の整数とするとき、同様に $k$ -Göbel数列 $\{x_n^{(k)}\}$ を $x_0^{(k)}=1$ および

$\displaystyle x_{n+1}^{(k)}=\frac{1+(x_0^{(k)})^k+(x_1^{(k)})^k+\cdots +(x_n^{(k)})^k}{n+1}$

によって定義することができます。このとき、新しい数列 $\{a_k\}_{k=2}^{\infty}$ を $k$ -Göbel数列が初めて整数でない値をとるときの数列の番号によって定義します*1。 $a_2=43, a_3=89$ です。

補題と同様にして $(n+1)x_{n+1}^{(k)}\equiv x_n^{(k)}((x_n^{(k)})^{k-1}+n)$ を証明することができるので、これを用いて $nx_n^{(k)} \not \equiv 0 \pmod{n}$ なる最小の $n$ を見つければ一応 $a_k$ を計算することはできます。