フィボナッチ数の判定式 (1) 　初等的証明

〔フィボナッチ数の判定式〕
正の整数 𝑁 に対して, 次の同値が成立する. 5𝑁² ± 4 のうちいずれかが平方数 ⇔ 𝑁 はフィボナッチ数.

この連続記事は, 以下を目標として記したものです.

フィボナッチ数の判定式に対して初等的な証明を与える.
ペル型方程式の解法について考察し, 二次体 $\ \mathbb{Q}(\sqrt{5})\$ とその整数環や単数といった代数的整数論の概念に触れる.

前提知識

漸化式など

(2) の記事 :

フィボナッチ数の判定式 (2) 二次体とその整数 - Arithmetica 算術ノート

(3) の記事 :

フィボナッチ数の判定式 (3) 二次体の整数の整除と単数 - Arithmetica 算術ノート

実験
初等的証明

実験

$\ N=1,\ 2,\ 3,\ 5,\ 8,\ 13,\ \ldots,\ 144\$ として $\ 5N^2\pm4\$ の値を具体的に計算すると次のようになり, 定理（ $\Longleftarrow$ ）の成立を確かめることができます.

\begin{align} &5\cdot1^2+4=9=3^2,&&5\cdot1^2-4=1=1^2.\\ &5\cdot2^2+4=24,&&5\cdot2^2-4=16=4^2.\\ &5\cdot3^2+4=49=7^2,&&5\cdot3^2-4=41.\\ &5\cdot5^2+4=129,&&5\cdot5^2-4=121=11^2.\\ &5\cdot8^2+4=324=18^2,&&5\cdot8^2-4=316.\\ &5\cdot13^2+4=849,&&5\cdot13^2-4=841=29^2.\\ &5\cdot21^2+4=2209=47^2,&&5\cdot21^2-4=2201.\\ &5\cdot34^2+4=5794,&&5\cdot34^2-4=5776=76^2.\\ &5\cdot55^2+4=15129=123^2,&&5\cdot55^2-4=15121.\\ &5\cdot89^2+4=39609,&&5\cdot89^2-4=39601=199^2.\\ &5\cdot144^2+4=10372=322^2,&&5\cdot144^2-4=10366. \end{align}

この結果を見ると, $\ n\$ が偶数のときは $\ 5F_n^2+4\$ が平方数になり, $\ n\$ が奇数のときは $\ 5F_n^2-4\$ が平方数になるであろうと予想が付きます. ただし $\ F_1=F_2=1\$ の二項が重複している $\ N=1\$ の場合のみ, $\ 5N^2\pm4\$ 両方が平方数になります. さらに, 平方数になる場合についてその平方根 (正の平方根) を抽出して並べれば, \begin{align} 1,\ 3,\ 4,\ 7,\ 11,\ 18,\ 29,\ 47,\ 76,\ 123,\ \ldots \end{align} のような数列が得られますが, これはリュカ数列と呼ばれ, フィボナッチ数列と相補的な関係にある数列です. リュカ数列はフィボナッチ数列と同様に, 漸化式 \begin{align} L_1=1,\ L_2=3,\ L_{n+2}=L_{n+1}+L_n \end{align} によって定義されます.

また, $\ 5N^2\pm4\$ が平方数であるとき, ある正の整数 $\ x\$ が存在して $\ 5N^2\pm4=x^2\$ つまり \begin{align} x^2-5N^2=\pm4 \end{align} が成り立つので, 証明の際にはこの方程式の正整数解について考察することになります. 以降, 文字を $\ x,y\$ で統一するために, $\ N\$ を $\ y\$ におきかえて $\ x^2-5y^2=\pm4\$ と書くことにします.

以上の考察から次の定理が予想されます. 次項でこの定理の初等的証明について述べたいと思います.

定理 1.1 方程式 $\ x^2-5y^2=\pm4\$ の正の整数解は $\ (x,y)=(L_n,F_n)\$ によって与えられる. さらに, 複号は $\ n\$ が偶数のときに正が対応し, 奇数のときに負が対応する.

$\ x=1,2,3,\ldots\$ を代入して計算すればわかるように, 初めの $\ 12\$ 個の解は以下の通りになります. \begin{align} \begin{array}{ll} (x,y)=(1,1) & (n=1)\\ (x,y)=(3,1) & (n=2)\\ (x,y)=(4,2) & (n=3)\\ (x,y)=(7,3) & (n=4)\\ (x,y)=(11,5) & (n=5)\\ (x,y)=(18,8) & (n=6)\\ (x,y)=(29,13) & (n=7)\\ (x,y)=(47,21) & (n=8)\\ (x,y)=(76,34) & (n=9)\\ (x,y)=(123,55) & (n=10)\\(x,y)=(199,89) & (n=11)\\(x,y)=(322,144) & (n=12). \end{array} \end{align}

初等的証明

補題 1.2 $\ x^2-5y^2=\pm4\$ の正の整数解 $\ (x,y)\$ に対して, \begin{align} \left(\frac{5y-x}{2},\frac{x-y}{2}\right) \end{align} を対応させる函数（写像） $\ f\$ を考える. $\ x^2-5y^2=\pm4\$ のいかなる正整数解 $\ (x,y)\$ も, 変換 $\ f\$ を繰り返すことによって, ついには $\ (1,1)\$ に帰着する.

証明. まず $\ (5y-x)/2=X,\ (x-y)/2=Y\$ とおくと $\ f\$ の対応は \begin{align} f\;\colon\;(x,y)\longmapsto(X,Y) \end{align} と表される. ここで以下の事項を示す.

$\ (1)\$ $\ y\ge2\$ のとき $\ X,\ Y\$ はともに正整数である.
$\ x^2-5y^2\$ は偶数であるから $\ x^2\$ と $\ 5y^2\$ の偶奇は等しく, $\ x\$ と $\ y\$ の偶奇も一致する. ゆえに $\ (5y-x)/2,\ (x-y)/2\$ はともに整数である. 次に, それぞれが正であることを背理法によって示す.
もし仮に $\ 5y\le x\$ とすれば \begin{align} x^2-5y^2\ge(5y)^2-5y^2=20y^2>4 \end{align} となって不適であり, $\ 5y-x\gt0.\$ 同様に, $\ x\le y\$ を仮定しても, $\ y\ge2\$ によって \begin{align} x^2-5y^2\le y^2-5y^2=-4y^2\lt -4 \end{align} の評価が得られる. これは不合理である. よって $\ X\gt0,\ Y\gt0.\$

$\ (2)\$ $\ (X,Y)\$ もまた方程式 $\ x^2-5y^2=\pm4\$ の解である.
代入して計算をすれば, \begin{align} X^2-5Y^2&=\left(\frac{5y-x}{2}\right)^2-5\left(\frac{x-y}{2}\right)^2\\&=\frac{-4x^2+20y^2}{4}\\&=-(x^2-5y^2)=\mp4. \end{align} すなわち $\ (X,Y)\$ もまた $\ x^2-5y^2=\pm4\$ を満たす. 加えて, $\ x^2-5y^2\$ と $\ X^2-5Y^2\$ の符号がつねに異なることも明らかになった.

$\ (3)\$ $\ y\ge2\$ のとき $\ Y\lt y.\$
対偶をとって $\ Y\ge y\ \Longrightarrow\ y=1\$ を証明する. $\ Y\ge y\$ のとき $\ (x-y)/2\geq y\$ すなわち $\ x\ge3y\$ であることを用いると, \begin{align} x^2-5y^2\ge(3y)^2-5y^2=4y^2\ge4. \end{align} 最後の不等号において等号が成り立つ $\ y=1\$ の場合を除いて, これは不適である.

ゆえに, $\ y\ge2\$ のときに $\ (x,y)\$ を $\ f\$ を通じて変換すれば, 新たな解 $\ (X,Y)\ \ (Y\lt y)\$ が得られるので, $\ x^2-5y^2=\pm4\$ のいかなる解も, $\ f\$ をいくらか演算すれば $\ y=1\$ の場合に帰着する. $\ y=1\$ のとき, $\ (x,y)=(1,1),\ (3,1)\$ が方程式の解であるが, $\ (3,1)\$ は $\ f\$ によって $\ (1,1)\$ に移されるから, $\ (1,1)\$ 以外のあらゆる解は, 繰り返し $\ f\$ をかける操作によって $\ (1,1)\$ に変換されるのである.

$\Box$

$\ f\$ は一対一の対応を持つ函数（全単射）なので, $\ f\$ による解の変換を次の図のように表したとき, 途中で枝分かれが起こることはありません.

f:id:yu200489144:20200229234345p:plain — 図1. 函数 $\ f\$ による解の変換

したがって, 最も小さい解 $\ (x,y)=(1,1)\$ から始めて矢印を逆向きにたどっていけば, すべての解を渡ることができます.

$\ (X,Y)\$ が解ならば, $\ f\$ を逆算して遡った $\ (x,y)\$ も解であることは次のようにして証明されます; 対偶を示す. $\ (x,y)\$ が解でなければ, つまり, $\ |x^2-5y^2|\neq4\$ ならば, 先述の $\ (2)\$ と全く同様な計算によって \begin{align} |X^2-5Y^2|=\cdots=|-(x^2-5y^2)|\neq4. \end{align} すなわち $\ (X,Y)\$ も解でない.

図においては, $\ f\$ の対応に基づいた順番で, 解を \begin{align} \ldots,\ (x_3,y_3),\ (x_2,y_2),\ (x_1,y_1)=(1,1) \end{align} と表現してあります. 加えて補題の証明中に導出した不等式 $\ Y\lt y\ \ (y\ge2)\$ から, $\ (x_2,y_2),\ (x_3,y_3),\ (x_4,y_4),\ \ldots\$ という羅列は $\ y\$ の値について小さい順 (昇順) に並んでいることがわかります. すなわち, $\ (x_n,y_n)\$ を次の規則:

$\ (1)\$ $\ y\ge2\$ つまり $\ n\ge3\$ のとき, $\ x^2-5y^2=\pm4\$ のすべての解を $\ y\$ の値について昇順に並べて $\ n\$ 番目にあたる解を $\ (x_n,y_n)\$ とする.

$\ (2)\$ $\ y=1\$ つまり $\ n=1,2\$ のときは, $\ y\$ の値が重複するので $\ (x_1,y_1)=(1,1),\ (x_2,y_2)=(3,1)\$ を規定する.

によって定義すると, $\ f\$ の変換は \begin{align} (x_{n+1},y_{n+1})\longmapsto(x_n,y_n) \end{align} と表されます.

これから, 補題を使って定理を証明してみせたいと思います.

定理 1.1 方程式 $\ x^2-5y^2=\pm4\$ の正整数解は $\ (x,y)=(L_n,F_n)\$ によって与えられる. さらに, 複号は $\ n\$ が偶数のときに正が対応し, 奇数のときに負が対応する.

証明. 補題によれば, $\ x^2-5y^2=\pm4\$ のいかなる正整数解 $\ (x,y)\$ も, 変換 $\ f\$ を繰り返すことによってついには $\ (1,1)\$ に移される. さて, この $\ f\$ によって各 $\ (x,y),\ (X,Y)\$ は一対一に対応し, かつ $\ (x,y)\$ が解であることと $\ (X,Y)\$ が解であることは同値であるから, $\ (1,1)\$ を $\ f\$ の逆変換によって移してゆけば, $\ x^2-5y^2=\pm4\$ のあらゆる正整数解が得られることになるであろう.
$\ f\$ の定義により, $\ n\ge2\$ に対し\begin{align} \left\{ \begin{array}{l} x_{n-1}=\dfrac{5y_n-x_n}{2} \\ y_{n-1}=\dfrac{x_n-y_n}{2} \end{array} \right. \end{align} が成立する. 第一式から $\ y_n=(x_n+2x_{n-1})/5,$ $y_{n-1}=(x_{n-1}+2x_{n-2})/5\$ である. これを第二式に代入して \begin{align} \frac{x_{n-1}+2x_{n-2}}{5}&=\frac{1}{2}\left(x_n-\frac{x_n+2x_{n-1}}{5}\right) \\ 2(2x_{n-2}+x_{n-1})&=5x_n-(x_n+2x_{n-1}).\end{align}式を整理すると $\ x_n=x_{n-1}+x_{n-2}\$ になり, $\ x_1=1,\ x_2=3\$ と合わせると $\ x_n=L_n.\$ 同様に $\ y_n=y_{n-1}+y_{n-2}\$ から $\ y_n=F_n\$ も得られる. ゆえに $\ x^2-5y^2=\pm4\$ の解は $\ (x,y)=(L_n,F_n)\$ によって与えられる.

また, 補題の証明中 $\ (2)\$ の論を見れば, $\ x^2-5y^2\$ と $\ X^2-5Y^2\$ の符号はつねに異なる. ここから定理の後半が得られる.

$\Box$

証明に用いた函数 $\ f\$ の対応は, 具体的に書き出すと次のようになります. ただし, $\ f^{-1}\$ は $\ f\$ の逆向きの変換をする函数（逆函数）であります.

f:id:yu200489144:20200229234428p:plain — 図2. 函数 $\ f,\ f^{-1}\$ による解の変換

函数 $\ f^{-1}\$ によって $\ (1,1)\$ を繰り返し変換してゆくと, その像が $\ x^2-5y^2=\pm4\$ のすべての正整数解をわたることを利用して, $\ x_n,\ y_n\$ の漸化式を作り, 再帰的に解を表現することができたというのが, 上記証明の流れになります.

こうして定理を初等的に証明することができたわけですが, 多くの方にとっては, まだ $\ 1\$ つほど疑問が残っていることでしょう. それは, なぜ \begin{align} f\;\colon\;(x,y)\longmapsto\left(\frac{5y-x}{2},\frac{x-y}{2}\right) \end{align} という函数を定義すると, 方程式に適する解を構成できたのかということです. (2) および (3) の記事では, $\ a+b\sqrt{5}\ \ (a,b\$ は有理数 $)\$ という形の「数」に着目し, この初等的証明の背景にあるもう一つの証明法について書きたいと思います. (次の記事のリンクは, このページの上のほうに貼ってあります. )

追記 : 今回紹介した解の変換を用いる初等的解法は, 実は幾何的に解釈することができます. 詳細は次の記事をご覧ください.

https://yu200489144.hatenablog.com/entry/2021/05/30/234100