2017-07-26

Fibonacci素数とF-完全数

Fibonacci 素数

完全数とは「自分自身以外の約数の総和が自分自身になる」ような正整数のことで、 $6,28,496,8128,\cdots$ と続きます。

これの仲間として「自分自身以外の約数の2乗和が自分自身の3倍になる」ような正整数を「F-完全数」と呼ぶことにしましょう。最初の3つのF-完全数は

$10\to 1^2+2^2+5^2=30=10\times 3\\65\to 1^2+5^2+13^2=195=65\times 3\\20737\to 1^2+89^2+233^2=62211=20737\times 3$

となります。

ところでこれらの数の約数を眺めていると不思議なことに気がつきます。そう、 $2,5,13,89,233$ は全てFibonacci数になっているのです。

種明かしをすると、実は次の定理が成り立つのです（Cai-Chen-Zhang,2015）。

定理. $n$ がF-完全数である必要十分条件は、共に素数である2つのFibonacci数 $F_{2m-1}, F_{2m+1}$ を用いて $n=F_{2m-1}F_{2m+1}$ と表されることである。

これを証明するためにLucas数について簡単な性質を確認しておきましょう。Lucas数とはFibonacci数の仲間で、 $L_1=1,L_2=3,L_{n+2}=L_{n+1}+L_n$ で定義されます。一般項を求めると次のようにまとめられます（証明略）。

補題. $\dfrac{L_n+F_n\sqrt5}{2}=\left(\dfrac{1+\sqrt5}{2}\right)^n.$

またFibonacci数との間には以下の関係があります。

補題. $L_n=F_{n+1}+F_{n-1}.$

これは帰納法により簡単に示すことができます。

それでは定理を示しましょう！

定理の証明. $n$ の約数が5個以上あったとし、小さい方から2つめ,3つめのものを $d_1, d_2$ とすると、相加相乗平均の不等式より

$1^2+d_1^2+(n/d_1)^2+d_2^2+(n/d_2)^2\geq1+2n+2n=1+4n$

となり不適。逆に約数が3個以下でも明らかに不適。ゆえに約数はちょうど4個なので、 $n=pq$ または $n=p^3$ （ $p,q$ は素数）と書ける。後者の場合約数の2乗和は $1+p^2+p^4\gt p\cdot p^3$ となるから $p\geq3$ では不適で、 $p=2$ でも成り立たない。よって $n=pq$ となる。

このとき満たすべき方程式は $1+p^2+q^2=3pq\Leftrightarrow (3p-2q)^2-5p^2=-4$ と変形できる。これはPell方程式だから解は

$(3p-2q,p)=(L_{2m+1},F_{2m+1})$

と書くことができる（Pell方程式については過去記事「奇跡の楕円曲線と144」内のリンクを参照）。補題と漸化式より

$q=\dfrac{3F_{2m+1}-L_{2m+1}}{2}=\dfrac{2F_{2m+1}+F_{2m+1}-F_{2m+2}-F_{2m}}{2}\\=\dfrac{2F_{2m+1}-2F_{2m}}{2}=F_{2m-1}$

となるから $n=pq=F_{2m-1}F_{2m+1}$ と書ける。逆にこの形ならばF-完全数であることも上の式変形を逆にたどれば示される。 $~~~\square$

ちなみにF-完全数が無限に存在するかどうかは未解決問題です。というのも、そもそもFibonacci数に素数が無限個存在するかが未解決だからです。なんとか私が生きている間に解決されてほしいものです。

2017-07-25

Fibonacci数の逆数和は無理数である

無理数 Fibonacci

【注意】この記事には横に長い数式が多く含まれます。小さい端末では画面を横向きにすることを推奨します。

皆さん、Fibonacci数は好きですか？好きですよね。私も大好きです。

今回は21世紀に生きるフィボナッチ・フリークなら必ず一度は証明を読んでおきたい"あの"定理を示しましょう。

Fibonacci数の逆数の和

$\displaystyle{\psi = \sum_{n=1}^\infty \dfrac{1}{F_n}=\dfrac{1}{1}+\dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{1}{8}+\cdots}$

はReciprocal Fibonacci Constantと呼ばれ、その値はおよそ

$\psi=3.35988566…$

となります。この数は無理数であることがAndré-Jeanninにより1989年に示されました。ここではDuverney(1997)（私が生まれた年！）により簡略化されたその証明を紹介したいと思います。

まず証明に必要な $q$ -指数・対数関数というものを定義します。

定義. $|q|\gt 1,|x|\lt |q|$ に対し

$\displaystyle{E_q(x)=1+\sum_{n=1}^{\infty}\dfrac{x^n}{(q^n-1)(q^{n-1}-1)\cdots(q-1)}}$

と定め、 $q$ -指数関数と呼ぶ。また

$\displaystyle{L_q(x)=\sum_{n=1}^\infty \dfrac{x^n}{q^n-1}}$

と定め、 $q$ -対数関数と呼ぶ。

これらは通常の指数・対数を定義する級数

$\displaystyle{e^x=1+\sum_{n=1}^\infty \dfrac{x^n}{n!},~~-\log(1-x)=\sum_{n=1}^\infty \dfrac{x^n}{n}}$

の自然数 $n$ の部分を $q^n-1$ というパラメータに置き換えたものになっています。このような置き換えは $q$ -類似と呼ばれています。

今回の証明の鍵となるのは次の性質です。

命題. $L_q(x)=x\dfrac{E'_q(-x)}{E_q(-x)}.$

証明. まず

$\displaystyle{E_q(x)-E_q\left(\frac{x}{q}\right)=\sum_{n=1}^\infty \dfrac{(x/q)^n(q^n-1)}{(q^n-1)\cdots(q-1)}=\frac{x}{q}E_q\left(\frac{x}{q}\right)}$

より

$E_q(x)=\left(1+\dfrac{x}{q}\right)E_q\left(\dfrac{x}{q}\right).$

これを繰り返し用いて

$\displaystyle{E_q(x)=\prod_{n=1}^\infty \left(1+\frac{x}{q^n}\right)}$

を得る。対数を取り微分すると

$\displaystyle{\dfrac{E'_q(x)}{E_q(x)}=\sum_{n=1}^\infty \frac{1}{q^n+x}.}\tag{1}$

一方で

$\displaystyle{L_q(x)-L_q\left(\frac{x}{q}\right)=\sum_{n=1}^\infty\left(\frac{x}{q}\right)^n=\frac{x}{q-x}}$

を繰り返し用いると

$\displaystyle{L_q(x)=\sum_{n=1}^\infty\frac{x}{q^n-x}.}\tag{2}$

$(1),(2)$ を比較すれば命題の式を得る。 $~~~\square$

それでは主定理を証明しましょう。

定理. $\displaystyle{\psi=\sum_{n=0}^\infty \frac{1}{F_n}}$ は無理数である。

証明. $\phi=\dfrac{1+\sqrt5}{2}, \bar\phi=\dfrac{1-\sqrt5}{2}$ と置く。 $\psi$ は $q$ -対数関数を使って

$\displaystyle{\psi=\sum_{n=1}^\infty \frac{\sqrt5}{\phi^n-\bar\phi^n}=\sum_{n=1}^\infty \frac{\sqrt5(-\phi)^n}{(-\phi^2)^n-1}=\sqrt5L_{-\phi^2}(-\phi)}$

と書ける。これが有理数 $\dfrac{-A}{B}$ （ $A,B$ は互いに素な整数）だったと仮定する。すると上の命題より

$AE_{-\phi^2}(\phi)-B\phi\sqrt5E'_{-\phi^2}(\phi)=0$

となる。 $E_q(x)$ の定義式に代入すると

$\displaystyle{A+\sum_{n=1}^\infty\frac{(A-Bn\sqrt5)(-\phi)^n}{\prod_{m=1}^n(1-(-\phi^2)^m)}=0.}$

ここで上の式の無限和を $n\leq N$ と $n\geq N+1$ に分割すると

$\displaystyle{A+\sum_{n=1}^N\frac{(A-Bn\sqrt5)(-\phi)^n}{\prod_{m=1}^n(1-(-\phi^2)^m)}=-\sum_{n=N+1}^\infty\frac{(A-Bn\sqrt5)(-\phi)^n}{\prod_{m=1}^n(1-(-\phi^2)^m)}.\tag{3}}$

分母を払えば

$\displaystyle{A\prod_{m=1}^N(1-(-\phi^2)^m)+\sum_{n=1}^N(A-Bn\sqrt5)(-\phi)^n\prod_{m=n+1}^N(1-(-\phi^2)^m)\\=-\sum_{n=N+1}^\infty\frac{(A-Bn\sqrt5)(-\phi)^n}{\prod_{m=N+1}^n(1-(-\phi^2)^m)}.}$

左辺の値を $X_N$ とし、右辺の無限和の中身を $R_n$ と置くと

$\displaystyle{|R_n|\leq\frac{(|A|+|B|\sqrt5)\cdot n\phi^n}{\prod_{m=N+1}^n\phi^{2m-1}}=\frac{(|A|+|B|\sqrt5)\cdot n}{\phi^{n^2-n-N^2}}\lt \frac{C_1n}{\phi^n}}$

と評価できる（ $C_1$ はある正の定数）。ゆえにある正の定数 $C'_1$ があって

$\displaystyle{|X_N|\lt\sum_{n=N+1}^\infty\frac{C_1n}{\phi^n}\lt \frac{C'_1N}{\phi^N}.}$

一方で $X_N$ の共役無理数( $\sqrt5$ を $-\sqrt5$ に置き換えたもの)を $\overline{X_N}$ と置くと、 $|\bar\phi|\lt 1$ なので、 $(1+|\bar\phi|^2)(1+|\bar\phi|^4)\cdots$ が $E_{\phi^2}(1)$ に収束することに注意すれば

$|\overline{X_N}|\lt C_2N^2$

（ $C_2$ はある正の定数）と評価できる。これらを合わせれば

$|X_N\overline{X_N}|\lt \dfrac{C_1'C_2N^3}{\phi^N}\to 0~~(N\to \infty).$

ここで $X_N$ は定義より代数的整数なので上式左辺は整数であり、ある $N_0$ が存在して $N\geq N_0-1\Rightarrow X_N=0$ でなければならない。このとき(3)式の左辺も $0$ になる。 $N=N_0-1,N_0$ として差分をとれば

$\dfrac{(A-BN_0\sqrt5)(-\phi)^{N_0}}{\prod_{m=1}^{N_0}(1-(-\phi^2)^m)}=0\\ \therefore\sqrt5=\dfrac{A}{BN_0}$

となり、 $\sqrt5$ の無理性に反する。ゆえに $\psi$ は無理数である。 $~~~\square$

ちなみに $\psi$ が超越数かどうかは未解決問題です（ぜひチャレンジしてみてください！）。一方でFibonacci数の逆数の2n乗和は超越数であることがわかっています。奇数乗和に関してわかっていることは少なく、ちょうどRiemannゼータ関数の特殊値のような状況になっています。これからどんな結果が出てくるか楽しみですね。

2017-07-24

あるサイズの巡回置換だけで任意の置換を作る

組み合わせ論

任意の置換は互換の積に表すことができます。では同じように、3元の巡回置換 $(i~j~k)$ （ $i,j,k$ は相異なる）だけを組み合わせて任意の置換を作ることはできるでしょうか？

答えはNoです。 $(i~j~k)=(i~k)(i~j)$ （置換は右から合成する）と書けるので、3元の巡回置換は偶置換です。偶置換の積は偶置換なので、この方法では偶置換しか作ることができません。

しかし、実は3元の巡回置換を使えば全ての偶置換を作ることができます。すなわち、 $S_n$ を $n$ 次の対称群、 $A_n$ を交代群とし、 $k$ 元の巡回置換で生成される $S_n$ の部分群を $T^{(k)}_n$ とすると、次が成り立ちます。

命題1. $~T^{(3)}_n=A_n.$

証明. 交わる2つの互換の積は3元の巡回置換に他ならず、交わらない2つの互換の積は $(i~j)(k~l)=(i~j~k)(j~k~l)$ なので、2つの互換の積は必ず $T^{(3)}_n$ に入る。 $A_n$ はこれらで生成されるから $A_n\subset T^{(3)}_n$ である。逆の包含は3元の巡回置換が偶置換であることから明らか。 $~~~\square$

実はより一般に次が成り立ちます。

命題2. $~k$ が奇数のとき $T^{(k)}_n=A_n.$

証明. 命題1より、任意の $k\geq 5$ について $(3~4~5)\in T^{(k)}_n$ を示せばよい（すると対称性から任意の3元の巡回置換を含む）。

$(k~(k-1)~\cdots~1)^2(1~2~4~3~5~6~~\cdots~k)^2=(1~2)(3~4)$

より $(1~2)(3~4)\in T^{(k)}_n$ であり、同様に $(1~2)(3~5)\in T^{(k)}_n$ なので $(3~4~5)=(1~2)(3~5)(1~2)(3~4)\in T^{(k)}_n$ となる。 $~~~\square$

では $k$ が偶数のときはどうなるでしょうか。

この場合、なんと任意の置換を作ることができます！以下の証明は箱(@o_ccah)さんから教えていただきました。

命題3. $~k$ が偶数のとき $T^{(k)}_n=S_n.$

証明. $k=2m$ とする。 $(1~2)\in T^{(k)}_n$ を示せばよい。

$\sigma = (2~4~6~\cdots~2m~1~3~5~\cdots~(2m-1))\\ \tau=(1~2~\cdots~2m)$

と置く。 $\tau^2\sigma^{-1}=(1~2)$ なので示された。 $~~~\square$

このように、あるタイプの置換で生成される置換の全体を求めることは、しばしば面白いパズルになります。皆さんも是非オリジナルの置換パズルを考えてみてください。

2017-07-22

振り子の幾何学

初等幾何

振り子に勢いよく初速を与えると、跳ね上がって糸がたるむことがありますね。

このとき、「糸がたるみ始める地点」と「球が落下して糸がピンと張る地点」の間には綺麗な関係があります。実は鉛直上方向から角度を測ると、角度の比（図の $\theta_1:\theta_2$ ）は必ず $1:3$ になるのです！（図は不正確ですがご容赦ください）

f:id:fibonacci_freak:20170722221034p:plain

この現象には次のような数学的な背景があります。

命題. 軸が $y$ 軸に平行な放物線上に4点 $A,B,C,D$ をとる。 $AC,BD$ の交点を $P$ とする。 $A,B,C,D,P$ から $x$ 軸に下ろした垂線の足を $A',B',C',D',P'$ とすると、

$A'P'\cdot P'C'=B'P'\cdot P'D'.$

f:id:fibonacci_freak:20170722223938p:plain

この命題は円に対する方べきの定理の放物線における類似なので、俗に「放べきの定理」などと呼ばれています。

証明. 適当に線形変換（行列表示の右上成分が $0$ のもの）と平行移動をすることで、放物線が $y=x^2-1$ 、 $AC:y=0$ 、 $BD:y=k(x-a)$ の場合に帰着できる。 $B,D$ の $x$ 座標をそれぞれ $\alpha,\beta$ とすると、これらは $x^2-1=k(x-a)$ の解なので

となり成り立っている。 $~~~\square$

これを使うと、円と放物線の交点の性質が明らかになります。

命題. $x$ 軸に平行な軸を持つ放物線と単位円が図のように4点 $A,B,C,D$ で交わっているとする。 $x$ 軸正方向から $A,B,C,D$ まで反時計回りに測った角の大きさをそれぞれ $a,b,c,d$ とすると

$a+b+c+d=0~\mathrm{mod}~2\pi.$

f:id:fibonacci_freak:20170722221701p:plain

証明. $2\pi$ の差は無視されるので、図のような角の取り方のみで示せばよい。 $AC,BD$ と $x$ 軸のなす角を $\theta,\phi$ とする。 $AC,BD$ の交点を $P$ とすると、通常の方べきの定理より

$AP\cdot PC=BP\cdot PD.$

一方上の命題から

$AP\cdot PC\cos^2\theta=BP\cdot PD\cos^2\phi.$

ゆえに $\theta=\phi$ がわかる。 $\dfrac{a+c}{2}=\dfrac{\pi}{2}-\theta=\dfrac{\pi}{2}-\phi=~\dfrac{(2\pi-b)+(2\pi-d)}{2}$ なので命題を得る。 $~~~\square$

さて、これがどう振り子と関係するのでしょうか。

振り子が跳ね上がる際、糸がたるみ始めるまでは球は円周上を動きます。糸がたるむと、球は重力によって放物線を描きます。たるむ瞬間に球に撃力が働くことはないので、運動方程式を考えれば、糸がたるむ直前と直後で位置・速度・加速度が一致しています。これはすなわちその点で円と放物線が3重に接していることを表しています。

そこで上の命題で3点 $A,C,D$ が一点に近づく極限を考えれば、それはまさしく冒頭の図で $\theta_1:\theta_2=1:3$ となることを表しています。

実際にこの現象が起きるのか気になった方は、ぜひ実験して確かめてみてください。

2017-07-20

根心の存在が自明に思える図

初等幾何

$O_1, O_2, O_3$ を中心とする3円が互いに2点ずつ( $A,A',B,B',C,C'$ )で交わっている状況を考えます（下図）。このとき3本の直線 $AA', BB', CC'$ は一点で交わります。これを3円の根心と言います。

f:id:fibonacci_freak:20170720195744p:plain

さらっと書いてしまいましたが、本当に一点で交わるの？と疑問に思われる方も多いでしょう（私も初めて聞いたときは驚きました）。このことは方べきの定理を用いて示すことができます。証明は以下に詳しく書かれています。

mathtrain.jp

しかし、実は根心の存在は直感的に明らかな形で理解する方法があります（厳密な証明には向きませんが）。

3つの三角形 $\triangle{O_1O_2A}, \triangle{O_2O_3B}, \triangle{O_3O_1C}$ に着目します。

f:id:fibonacci_freak:20170720200752p:plain

ここでこの図を3次元空間内のある平面に置かれたものと考え、それぞれの三角形を $O_1O_2, O_2O_3, O_3O_1$ を軸に回転させると、下図のように三角錐を組み立てることができます。

f:id:fibonacci_freak:20170720201135p:plain

回転させる過程を上から見れば、 $A,B,C$ はそれぞれ直線 $AA',BB',CC'$ 上を動くので、出来上がる三角錐の頂点（を上から見た点）がちょうど根心になっています。

3次元に生きていて本当によかったですね。

2017-07-20

奇跡の楕円曲線と144

Fibonacci

私が最も好きな不定方程式の一つに、次のものがあります。

$y^2=x^3+20x$

いわゆる楕円曲線の一種です。この方程式の整数解は全部でいくつあるでしょうか？

まず方程式の形から $x\geq0$ がわかります。順に試していけばすぐに $(x,y)=(0,0),(4,\pm12),(5,\pm15)$ という解が見つかります。ここから先はなかなか解が現れず、これで全てであるかのように思われます。

しかしこの方程式はそんなつまらないものではありません。実はこんな解もあるのです。

$(x,y)=(720,\pm19320)$

大きい解ですね。実際計算してみると

$19320^2=373262400\\720^3+20\cdot 720=373248000+14400=373262400$

となり、確かに解になっています。一般にこのような大きな解がある不定方程式は手計算では解くことが難しいです。しかしこの方程式に限っては、実に鮮やかな方法でこの解を求めることができます。まさに奇跡の楕円曲線というわけです。

以下の方法は私が今年たまたま見つけたものですが（恐らくもっと昔から知られているとは思いますが）、発見した日の晩は興奮して眠れませんでした。

さて、準備としてPell方程式について復習しておきましょう。

補題. $~x^2-5y^2=4$ の正整数解は

$\dfrac{x+y\sqrt5}{2}=\phi^{2n}~(n\geq1)$

なる $(x,y)$ で与えられる。ここで $\phi=\frac{1+\sqrt5}{2}$ （黄金比）。

証明は以下のサイトなどに丁寧にまとめられています。

IMOmath: Pell's Equations

それでは本題の証明に入りましょう。

命題. $~y^2=x^3+20x$ の整数解は $(x,y)=(0,0),(4,\pm12),(5,\pm15),(720,\pm19320)$ のみである。

証明. $x\gt0$ のみ考えればよい。 $y^2=x(x^2+20)$ と因数分解する。 $x$ が平方数の場合、 $x^2+20$ も平方数なので $x=4,y=\pm12$ となる。平方数でない場合 $x=s^2m$ （ $m$ は平方因子を持たない）とすると $m$ は $x^2+20$ を割り切るので、特に $20$ を割り切る。ゆえに $m=2,5,10$ のいずれかである。

$m=2$ の場合、 $x(x^2+20)=(2s)^2(2s^4+10)$ で、 $2s^4+10\equiv 2~\mathrm{mod}~5$ は平方数とはなりえないので不適（ $2$ は $\mathrm{mod}~5$ で平方元でない）。

$m=10$ の場合、もとの方程式に代入すれば

$\left(\dfrac{y}{10}\right)^2=2s^2(5s^4+1)$

となる。右辺の素因数 $2$ の数を考えれば $s$ は奇数であり、また左辺は偶数なので $4Y^2$ と書ける。このとき

$\left(\dfrac{Y}{s}\right)^2=\dfrac{5s^4+1}{2}\equiv3~\mathrm{mod}~5$

なので不適（ $3$ は $\mathrm{mod}~5$ で平方元でない）。

$m=5$ の場合、もとの方程式に代入すれば

$\left(\dfrac{y}{5}\right)^2=s^2(5s^4+4).$

ゆえに $5s^4+4$ は平方数であり $b^2$ と書くことができる。

$b^2-5s^4=4$

なので補題（Pell方程式）よりある $n$ が存在して

$\dfrac{b+s^2\sqrt5}{2}=\phi^{2n}$

$\therefore s^2=\dfrac{\phi^{2n}-\bar\phi^{2n}}{\sqrt5}=F_{2n}$

(ただし $\bar\phi=\dfrac{1-\sqrt5}{2}$ 、 $F_n$ はFibonacci数)となり、 $s^2$ は偶数番目のFibonacci数かつ平方数である。Cohnの定理によれば、このような数は $1$ と $144$ しか存在しない。これについては以下の記事に詳しい証明がある。

integers.hatenablog.com

よって $x=5s^2=5$ または $720$ となり、このときそれぞれ $y=\pm15,\pm19320$ が解を与える。 $~~~\square$

というわけで、 $720$ という解はFibonacci平方数である $144$ に由来していたのです。

ところで $144$ は $12$ の二乗で、なおかつ $12$ 番目のFibonacci数です。 $12$ という数字は数学の至る所で重要な役割を果たしています。モジュラー形式 $\Delta$ のウェイトは $12$ ですし、代数曲面論のNoetherの公式には $12$ が含まれます。そしてそれらを繋ぐ組み合わせ論的な定理である $12$ 点定理というものも知られています。私は密かに、Fibonacci平方数144もこれらの $12$ と関係しているのでは、などと妄想しています。

2017-07-17

石取りゲームとFibonacci数

組み合わせ論 Fibonacci

2人で次のようなゲームをします。

石が $n$ 個積まれている( $n\geq2$ )。交互に1つ以上の石を取り去り、最後の石を取れば勝ちである。ただし次のルールを守らなければいけない。

(1) 先手は最初に全ての石をとってはいけない。

(2) 相手が直前に取った石の数の2倍より多く取ってはいけない。

さて、このゲームに必勝法はあるのでしょうか？

実は次のことが成り立ちます。

命題. 上のゲームは $n$ がFibonacci数のとき後手必勝、それ以外のとき先手必勝である。

ここでFibonacci数とは $F_1=F_2=1, F_{n+2}=F_{n+1}+F_n$ で定義される数列です。これを示すには次の事実を用います。

定理. 任意の正整数 $n$ は、隣り合わないいくつかのFibonacci数 $F_m(m\neq 1)$ の和に一意的に表される。これをZeckendorf表示という。

たとえば $53=34+13+5+1=F_9+F_7+F_5+F_2$ などです。

証明. $n=1$ の時は明らか。 $n\gt 1$ のとき $F_m\leq n$ なる最大の $m$ をとると、帰納法の仮定より $n-F_m$ は一意的なZeckendorf表示を持つ。最大性より $n-F_m$ のZeckendorf表示には $F_{m-1}$ 未満のFibonacci数のみ現れるので（そうでなければ $n\geq F_{m+1}$ となってしまう）、これと $F_m$ を合わせれば $n$ のZeckendorf表示が得られる。

一意性を示すには、 $F_m$ を使わなければならないことを示せばよい。 $F_m$ 未満のFibonacci数のみを用いて表示できる最大の整数は $F_{m-1}+F_{m-3}+\cdots+1$ だが、これは漸化式より $F_{m-2}+F_{m-3}+\cdots+F_1=F_m-1$ 以下であり、これらで $n$ を表すことはできない（最後の式は帰納法で簡単に示せる）。 $\square$

さて、Zeckendorf表示を使って上のゲームの必勝法を作ってみましょう。基本的なアイディアは「残りの石の数をZeckendorf表示したとき現れる最小のFibonacci数を取り除く」ことです。

命題の証明. 「 $x$ のZeckendorf表示に現れる最小のFibonacci数」を $F_{Z(x)}$ と書くことにする。

$n$ がFibonacci数でなければ、先手は $a=F_{Z(n)}$ 個だけ取る。するとZeckendorf表示の性質より残りの数 $n-a$ は

$Z(n-a)\geq Z(n)+2$

をみたす。このときFibonacci数の漸化式より $F_{Z(n)+2}\gt 2F_{Z(n)}$ なので後手は $F_{Z(n)+2}$ 個以上の石を取ることができず、したがって全ての石を取ることはできない、これを繰り返せば勝てるので、後手が次に取る個数に関わらず繰り返せることを示そう。

後手が $b$ 個取ったとし、残りの石の数 $n-a-b$ が $F_{Z(n-a-b)}\gt 2b$ を満たすと仮定して矛盾を導く。 $b$ より真に大きい最小のFibonacci数を $F_c$ とすると、仮定より特に

$F_{Z(n-a-b)}\gt 2b\geq 2F_{c-1}\geq F_c$

なので

$Z(n-a-b)\geq c+1.\tag{1}$

一方で後手が操作する前には

$F_{Z(n-a)}\geq F_{Z(n)+2}\gt 2F_{Z(n)}\geq b$

だったので $c$ の最小性から

$Z(n-a)\geq c.\tag{2}$

等号が成立するときは

$n-a-b=n-a-F_{Z(n-a)}+(F_{Z(n-a)}-b)$

で、括弧内のZeckendorf表示が $2b$ 以下のFibonacci数を持つので仮定と矛盾。成立しないときは(1)と(2)を比較すれば $Z(b)\geq c$ となり矛盾する（一般に $x$ がFibonacci数の時 $Z(x-y)\geq\min\{Z(x),Z(y)\}-1$ であることに注意せよ）。これで先手必勝がわかった。

$n$ がFibonacci数 $F_m$ だったとする。先手の操作後にまたFibonacci数 $F_{m'}$ が残ると後手が勝つ。なぜなら先手が取る石の数は $F_m-F_{m'}\geq F_{m-2}$ であり、後手は $F_{m'}(\leq F_{m-1}\leq 2F_{m-2})$ 個の石をすべて取れるからである。そうでない場合、先ほどの議論を後手に適用することでやはり後手が勝てることがわかる. $\square$

こんな単純なゲームにFibonacci数が現れるのは面白いですね。