COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

Fibonacci 数列

理論

Fibonacci 数列・Lucas 数列

導入≪アダムの時代の人口≫

 アダムの時代の人々は $\ell$ 歳まで死ぬことはなく, $m$ 歳で結婚したとする. そして, 結婚してから $m$ 年後ごとに男の子 $1$ 人, 女の子 $1$ 人を産み続けたとして, アダムが死ぬ直前の人口 $P$ を求めてみよう. 簡単のため, $m$ を $\ell$ の約数とする. アダムとエバの誕生から $m$ 年が経つまでを第 $1$ 期とし, それから $m$ 年ごとに第 $2$ 期, 第 $3$ 期, ... と名付ける. 第 $n$ 期の人口を $P_n,$ 子どもの数を $C_n$ で表す. このとき, $P_1 = P_2 = 2.$ また, $n+2 \leqq \ell /m$ のとき, \[ P_{n+2} = C_{n+2}+P_{n+1}\] であり, 第 $n+2$ 期の子どもの数 $C_{n+2}$ は第 $n+1$ 期の大人の数に等しく, それは第 $n$ 期の人口 $P_n$ に等しいから \[ P_{n+2} = P_n+P_{n+1}.\] この式から順次 $P_3 = P_1+P_2 = 2+2 = 4,$ $P_4 = P_2+P_3 = 2+4 = 6,$ $\cdots$ と計算していくと, $P = P_{\ell /m}$ が求まる. $\ell = 930,$ $m = 30$ のとき $P = P_{31} = 2692538,$ $\ell = 900$ であり, $m = 20$ のとき $P = P_{45} = 2269806340$ である. $F_n = P_n/2$ とおいて得られる数列 $\{ F_n\}$ は Fibonacci 数列と呼ばれる.

定義≪Fibonacci 数列・Lucas 数列≫

(a)
\[ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_n+F_{n+1}\] により定まる数列を Fibonacci 数列(Fibonacci sequence)と呼び, その項を Fibonacci 数(Fibonacci number)と呼ぶ.
(b)
\[ L_0 = 2, \quad L_1 = 1, \quad L_{n+2} = L_n+L_{n+1}\] により定まる数列を Lucas 数列(Lucas sequence)と呼び, その項を Lucas 数(Lucas number)と呼ぶ.

例≪Fibonacci 数・Lucas 数≫

(a)
$20$ 番目までの Fibonacci 数を列挙すると, \begin{align*} F_0 &= 0, & F_1 &= 1, & F_2 &= 1, \\ F_3 &= 2, & F_4 &= 3, & F_5 &= 5, \\ F_6 &= 8, & F_7 &= 13, & F_8 &= 21, \\ F_9 & = 34, & F_{10} &= 55, & F_{11} &= 55, \\ F_{12} &= 144, & F_{13} &= 233, & F_{14} &= 377, \\ F_{15} &= 610, & F_{16} &= 987, & F_{17} &= 1597, \\ F_{18} &= 2584, & F_{19} &= 4181, & F_{20} &= 6765. \end{align*}
(b)
$20$ 番目までの Lucas 数を列挙すると, \begin{align*} L_0 &= 2, & L_1 &= 1, & L_2 &= 3, \\ L_3 &= 4, & L_4 &= 7, & L_5 &= 11, \\ L_6 &= 18, & L_7 &= 29, & L_8 &= 47, \\ L_9 & = 76, & L_{10} &= 123, & L_{11} &= 199, \\ L_{12} &= 322, & L_{13} &= 521, & L_{14} &= 843, \\ L_{15} &= 1364, & L_{16} &= 2007, & L_{17} &= 3571, \\ L_{18} &= 5778, & L_{19} &= 9349, & L_{20} &= 15127. \end{align*}

定理≪Binet の公式, 1843≫

 $x^2-x-1 = 0$ の正の解を $\alpha,$ 負の解を $\beta$ とおく.
(a)
Fibonacci 数列の一般項は, \[ F_n = \frac{\alpha ^n-\beta ^n}{\alpha -\beta} = \frac{1}{\sqrt 5}\left(\left(\frac{1\!+\!\sqrt 5}{2}\right) ^n\!-\!\left(\frac{1\!-\!\sqrt 5}{2}\right) ^n\right).\]
(b)
Lucas 数列の一般項は, \[ L_n = \alpha ^n+\beta ^n = \left(\frac{1\!+\!\sqrt 5}{2}\right) ^n\!+\!\left(\frac{1\!-\!\sqrt 5}{2}\right) ^n.\]

証明

(a)
$\{ F_{n+1}-\beta F_n\},$ $\{ F_{n+1}-\alpha F_n\}$ がそれぞれ公比 $\alpha,$ $\beta$ の等比数列になるように $\alpha,$ $\beta$ の値を定める. これが成り立つとき, \begin{align*} F_{n+2}-\beta F_{n+1} = \alpha (F_{n+1}-\beta F_n), \\ F_{n+2}-\alpha F_{n+1} = \beta (F_{n+1}-\alpha F_n) \end{align*} となり \[ F_{n+2} = (\alpha +\beta )F_{n+1}-\alpha\beta F_n\] となるから, 漸化式との比較により \[\alpha +\beta = 1, \quad \alpha\beta = -1\] が成り立てば良い. そこで, $x^2-x-1 = 0$ の正の解を $\alpha,$ 負の解を $\beta$ とおく. このとき, \begin{align*} F_{n+1}-\beta F_n &= (F_1-\beta F_0)\alpha ^n = \alpha ^n \quad \cdots [1], \\ F_{n+1}-\alpha F_n &= (F_1-\alpha F_0)\beta ^n = \beta ^n \quad \cdots [2]. \end{align*} $[1]-[2]$ より \[ (\alpha -\beta )F_n = \alpha ^n-\beta ^n\] となるから, 求める等式が得られる.
(b)
(a) と同様にして, \begin{align*} L_{n+1}\!-\!\beta L_n &= (L_1\!-\!\beta L_0)\alpha ^n = (1\!-\!2\beta )\alpha ^n \quad \cdots [1], \\ L_{n+1}\!-\!\alpha L_n &= (L_1\!-\!\alpha L_0)\beta ^n = (1\!-\!2\alpha )\beta ^n \quad \cdots [2]. \end{align*} $[1]-[2]$ より \begin{align*} &(\alpha -\beta )L_n \\ &= (1-2\beta )\alpha ^n-(1-2\alpha )\beta ^n \\ &= \alpha ^n-2\alpha ^n\beta -\beta ^n+2\alpha\beta ^n \\ &= (1-\beta )\alpha ^n-\alpha ^n\beta +\alpha\beta ^n-\beta ^n(1-\alpha ) \\ &= \alpha ^{n+1}-\alpha ^n\beta +\alpha\beta -\beta ^{n+1} \quad (\because\alpha +\beta = 1) \\ &= (\alpha -\beta )(\alpha ^n+\beta ^n) \end{align*} となるから, 求める等式が得られる.

定理≪Fibonacci 数列・Lucas 数列の項の比≫

\[\lim _{n\to\infty}\frac{F_{n+1}}{F_n} = \lim _{n\to\infty}\frac{L_{n+1}}{L_n} = \alpha, \quad \lim _{n\to\infty}\frac{L_n}{F_n} = \sqrt 5.\]

証明

\begin{align*} \frac{F_{n+1}}{F_n} &= \frac{\alpha ^{n+1}-\beta ^{n+1}}{\alpha ^n-\beta ^n} = \frac{\alpha -\beta (\beta /\alpha )^n}{1-(\beta /\alpha )^n} \\ &\to \frac{\alpha -\beta\cdot 0}{1-0} = \alpha \quad (n \to \infty ), \\ \frac{L_{n+1}}{L_n} &= \frac{\alpha ^{n+1}+\beta ^{n+1}}{\alpha ^n+\beta ^n} = \frac{\alpha +\beta (\beta /\alpha )^n}{1+(\beta /\alpha )^n} \\ &\to \frac{\alpha +\beta\cdot 0}{1+0} = \alpha \quad (n \to \infty ), \\ \frac{L_n}{F_n} &= \sqrt 5\cdot\frac{\alpha ^n+\beta ^n}{\alpha ^n-\beta ^n} = \sqrt 5\cdot\frac{1+(\beta /\alpha )^n}{1-(\beta /\alpha )^n} \\ &\to \sqrt 5\cdot\frac{1+0}{1-0} = \sqrt 5 \quad (n \to \infty ). \end{align*}

補足≪Fibonacci 数列の項の比の収束の幾何学的意味≫

 「フィボナッチ数列」の隣り合う項の比が「黄金比」に収束することは, 正方形から始めて, 長方形の長い方の辺に正方形を継ぎ足すことで長方形を大きくするという操作を繰り返すときに, 辺の長さの比が「黄金比」に近づいていくことを意味する. 辺の長さの比が黄金比である長方形は「黄金長方形」と呼ばれる.

例≪Fibonacci 数の近似値≫

 Binet の公式を応用して Fibonacci 数の近似値を, 次のようにして求めることができる. \[ F_n = \frac{\alpha ^n-\beta ^n}{\sqrt 5} = \frac{\alpha ^n}{\sqrt 5}\left( 1-\left(\frac{\beta}{\alpha}\right)^n\right)\] であり, $|\beta\alpha ^{-1}| < 1$ より \[\lim _{n\to\infty}\left(\frac{\beta}{\alpha}\right) ^n = 0\] だから, \[ F_n \fallingdotseq \frac{\alpha ^n}{\sqrt 5}.\] 例えば, $F_{32}$ の近似値 \[\frac{1.62^{32}}{2.24} \fallingdotseq 2260645\] は実際の値 $2178309$ にかなり近い.

定理≪Fibonacci 数列と Lucas 数列の相互関係≫

 任意の非負整数 $n$ に対して,
(a)
$L_{n+1} = F_n+F_{n+2}.$ 
(b)
$F_{2n} = F_nL_n.$ 
(b)'
$F_{2^n} = \prod _{k = 0}^{n-1}L_{2^k}.$ 

証明

(a)
Binet の公式により, \begin{align*} &L_{n+1}-F_{n+2} \\ &= \alpha ^{n+1}+\beta ^{n+1}-\frac{\alpha ^{n+2}-\beta ^{n+2}}{\alpha -\beta} \\ &= \frac{(\alpha -\beta )(\alpha ^{n+1}+\beta ^{n+1})-\alpha ^{n+2}+\beta ^{n+2}}{\alpha -\beta} \\ &= \frac{\alpha\beta ^{n+1}-\alpha ^{n+1}\beta}{\alpha -\beta} = \frac{-\alpha\beta (\alpha ^n-\beta ^n)}{\alpha -\beta} \\ &= \frac{\alpha ^n-\beta ^n}{\alpha -\beta} \quad (\because\alpha\beta = -1) \\ &= F_n. \end{align*}
(b)
Binet の公式により, \[ F_nL_n = \frac{\alpha ^n-\beta ^n}{\alpha -\beta}(\alpha ^n+\beta ^n) = \frac{\alpha ^{2n}-\beta ^{2n}}{\alpha -\beta} = F_{2n}.\]
(b)'
$n \geqq 1$ のとき, (b) により, \[ F_{2^n} = F_{2\cdot 2^{n-1}} = F_{2^{n-1}}L_{2^{n-1}}.\] $n \geqq 2$ のとき, $F_{2^{n-1}} = F_{2^{n-2}}L_{2^{n-2}}$ だから, \[ F_{2^n} = F_{2\cdot 2^{n-1}} = F_{2^{n-2}}L_{2^{n-2}}L_{2^{n-1}}.\] この操作を続けると, \[ F_{2^n} = F_{2^0}\prod _{k = 0}^{n-1}L_{2^k} = \prod _{k = 0}^{n-1}L_{2^k}.\]

例≪$2$ の累乗番目の Fibonacci 数≫

\[ F_{32} = L_1L_2L_4L_8L_{16} = 1\cdot 3\cdot 7\cdot 47\cdot 2207 = 2178309.\]

定理≪偶数番目の Lucas 数≫

 任意の非負整数 $n$ に対して, \[ L_{2n} = L_n{}^2+2(-1)^{n+1}.\]

証明

 Binet の公式により, \begin{align*} L_{2n} &= \alpha ^{2n}+\beta ^{2n} = (\alpha ^n+\beta ^n)^2-2(\alpha\beta )^n \\ &= L_n{}^2-2(-1)^n = L_n{}^2+2(-1)^{n+1}. \end{align*}

加法定理

定理≪Fibonacci 数列・Lucas 数列の加法定理≫

 任意の非負整数 $m,$ $n$ に対して, 次が成り立つ.
(a)
$F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1}$ (Carlitz, 1964).
(b)
$L_{m+n+1} = F_mL_n+F_{m+1}L_{n+1}$ (Carlitz, 1964).
(c)
$2F_{m+n} = F_mL_n+L_mF_n$ (Ferns, 1967).
(d)
$2L_{m+n} = 5F_mF_n+L_mL_n$ (Ferns, 1967).

証明

 $m$ を固定し, $n$ に関する帰納法で \begin{align*} F_{m+n+1} &= F_mF_n+F_{m+1}F_{n+1} \quad \cdots [\text a]_n, \\ L_{m+n+1} &= F_mL_n+F_{m+1}L_{n+1} \quad \cdots [\text b]_n, \\ 2F_{m+n} &= F_mL_n+L_mF_n \quad \cdots [\text c]_n, \\ 2L_{m+n} &= 5F_mF_n+L_mL_n \quad \cdots [\text d]_n \end{align*} を示す.
(a)
(i)
$F_0 = 0,$ $F_1 = F_2 = 1$ より \begin{align*} &F_mF_0+F_{m+1}F_1 = F_{m+1}, \\ &F_mF_1+F_{m+1}F_2 = F_m+F_{m+1} = F_{m+2} \end{align*} となるから, $[\text a]_0,$ $[\text a]_1$ が成り立つ.
(ii)
与えられた非負整数 $n$ に対して, $[\text a]_n,$ $[\text a]_{n+1}$ の成立を仮定する. このとき, \begin{align*} &F_{m+n+3} \\ &= F_{m+n+1}+F_{m+n+2} \\ &= F_mF_n+F_{m+1}F_{n+1}+F_mF_{n+1}+F_{m+1}F_{n+2} \\ &= F_m(F_n+F_{n+1})+F_{m+1}(F_{n+1}+F_{n+2}) \\ &= F_mF_{n+2}+F_{m+1}F_{n+3} \end{align*} となり, $[\text a]_{n+2}$ が成り立つ.
(b)
(i)
$L_0 = 2,$ $L_1 = 1,$ $L_2 = 3$ より \begin{align*} &F_mL_0+F_{m+1}L_1 = 2F_m+F_{m+1} \\ &= F_m+(F_m+F_{m+1}) = F_m+F_{m+2} \\ &= L_{m+1}, \\ &F_mL_1+F_{m+1}L_2 = F_m+3F_{m+1} \\ &= 2F_{m+1}+(F_m+F_{m+1}) = 2F_{m+1}+F_{m+2} \\ &= F_{m+1}+(F_{m+1}+F_{m+2}) = F_{m+1}+F_{m+3} \\ &= L_{m+2} \end{align*} となるから, $[\text b]_0,$ $[\text b]_1$ が成り立つ.
(ii)
与えられた非負整数 $n$ に対して, $[\text b]_n,$ $[\text b]_{n+1}$ の成立を仮定する. このとき, \begin{align*} &L_{m+n+3} \\ &= L_{m+n+1}+L_{m+n+2} \\ &= F_mL_n+F_{m+1}L_{n+1}+F_mL_{n+1}+F_{m+1}L_{n+2} \\ &= F_m(L_n+L_{n+1})+F_{m+1}(L_{n+1}+L_{n+2}) \\ &= F_mL_{n+2}+F_{m+1}L_{n+3} \end{align*} となり, $[\text b]_{n+2}$ が成り立つ.
(c)
(i)
$F_0 = 0,$ $F_1 = 1,$ $L_0 = 2,$ $L_1 = 1$ より \begin{align*} &F_mL_0+L_mF_0 = 2F_m, \\ &F_0L_1+L_0F_1 = 2F_1 \quad (m = 0), \\ &F_mL_1+L_mF_1 = F_m+L_m \\ &= F_m+F_{m-1}+F_{m+1} = 2F_{m+1} \quad (m \geqq 1) \end{align*} となるから, $[\text c]_0,$ $[\text c]_1$ が成り立つ.
(ii)
与えられた非負整数 $n$ に対して, $[\text c]_n,$ $[\text c]_{n+1}$ の成立を仮定する. このとき, \begin{align*} &2F_{m+n+2} \\ &= 2F_{m+n}+2F_{m+n+1} \\ &= F_mL_n+L_mF_n+F_mL_{n+1}+L_mF_{n+1} \\ &= F_m(L_n+L_{n+1})+L_m(F_n+F_{n+1}) \\ &= F_mL_{n+2}+L_mF_{n+2} \end{align*} となり, $[\text c]_{n+2}$ が成り立つ.
(d)
(i)
$F_0 = 0,$ $F_1 = 1,$ $L_0 = 2,$ $L_1 = 1$ より \begin{align*} &5F_mF_0+L_mL_0 = 2L_m, \\ &5F_0F_1+L_0L_1 = 2L_1 \quad (m = 0), \\ &5F_mF_1+L_mL_1 = 5F_m+L_m \\ &= 5F_m+F_{m-1}+F_{m+1} = 4F_m+2F_{m+1} \\ &= 2(F_m+F_{m+2}) = 2L_{m+1} \quad (m \geqq 1) \end{align*} となるから, $[\text d]_0,$ $[\text d]_1$ が成り立つ.
(ii)
与えられた非負整数 $n$ に対して, $[\text d]_n,$ $[\text d]_{n+1}$ の成立を仮定する. このとき, \begin{align*} &2L_{m+n+2} \\ &= 2L_{m+n}+2L_{m+n+1} \\ &= 5F_mF_n+L_mL_n+5F_mF_{n+1}+L_mL_{n+1} \\ &= 5F_m(F_n+F_{n+1})+L_m(L_n+L_{n+1}) \\ &= 5F_mF_{n+2}+L_mL_{n+2} \end{align*} となり, $[\text d]_{n+2}$ が成り立つ.
以上より, 任意の非負整数 $m,$ $n$ に対して題意が成り立つ.

整除関係

補題

 任意の非負整数 $n$ に対して, $F_n,$ $F_{n+1}$ は互いに素である.

証明

 $d$ を $F_n,$ $F_{n+1}$ の任意の正の公約数とする. $n > 1$ のとき, $d$ は $F_{n+1}-F_n = F_{n-1}$ を割り切れる. これを繰り返すと, $d$ は $F_1 = 1$ を割り切るから, $d = 1.$ ゆえに, $F_n,$ $F_{n+1}$ は互いに素である.

補題

 正整数 $m,$ $q$ に対して, $F_m$ は $F_{mq}$ を割り切る.

証明

 $m$ を固定し, $q$ に関する帰納法で示す.
(i)
$F_{m\cdot 0} = F_0 = 0$ は $F_m$ で割り切れるから, $q = 0$ のとき成り立つ.
(ii)
与えられた非負整数 $q$ に対して $F_{mq}$ が $F_m$ で割り切れるとする. このとき, $d = F_{mq}/F_m$ は整数だから, \begin{align*} F_{m(q+1)} &= F_{mq+m-1+1} \\ &= F_{mq}F_{m-1}+F_{mq+1}F_m \quad (\because (1)) \\ &= dF_mF_{m-1}+F_{mq+1}F_m \\ &= F_m(dF_{m-1}+F_{mq+1}) \end{align*} は $F_m$ で割り切れる.
以上より, 任意の正整数 $m,$ $q$ に対して $F_{mq}$ は $F_m$ で割り切れる.

定理≪Fibonacci 数の整除関係≫

 任意の非負整数 $m,$ $n$ に対して, 次が成り立つ.
(1)
$n \neq 0$ のとき, $(F_m,\ F_n) = F_{(m,\ n)}.$
(2)
$m \leqq n$ のとき,
$m$ は $n$ を割り切る$\iff$ $F_m$ は $F_n$ を割り切る.
(3)
$n \neq 4$ のとき, $F_n$ が素数ならば $n$ は素数である.
(4)
$\mu$ を $\mu > 1$ なる整数とする. $\mu$ で割り切れるような最小の Fibonacci 数が $F_m$ であるとき,
$\mu$ は $F_n$ を割り切る $\iff$ $m$ は $n$ を割り切る.
特に,
  • $F_n$ が $2$ の倍数 $\iff$ $n$ が $3$ の倍数.
  • $F_n$ が $3$ の倍数 $\iff$ $n$ が $4$ の倍数.
  • $F_n$ が $5$ の倍数 $\iff$ $n$ が $5$ の倍数.
  • $F_n$ が $7$ の倍数 $\iff$ $n$ が $8$ の倍数.
  • $F_n$ が $11$ の倍数 $\iff$ $n$ が $10$ の倍数.
  • $F_n$ が $13$ の倍数 $\iff$ $n$ が $7$ の倍数.
ここで, 整数 $a,$ $b$ の最大公約数を $(a,\ b)$ で表した.

証明

(1)
(I)
$m = 0$ のとき. \[ (F_0,\ F_n) = (0,\ F_n) = F_n = F_{(0,\ n)}.\]
(II)
$m \neq 0$ のとき. $m \leqq n$ として一般性を失わない. $r_{-1} = n,$ $r_0 = m$ として, 整数 $q_k,$ $r_k$ を \[ r_{k-2} = r_{k-1}q_k+r_k, \quad 0 \leqq r_k < r_{k-1}\] により帰納的に定めると, ある正整数 $\ell$ に対して $r_\ell = 0$ となる. このとき, Euclid の互除法により $(m,\ n) = r_{\ell -1}$ が成り立つ. $m \leqq n$ より $mq_1 \geqq m > 0$ であることに注意すると, Carlitz の加法定理により, \[ F_n = F_{mq_1-1+r_1+1} = F_{mq_1-1}F_{r_1}+F_{mq_1}F_{r_1+1}.\] $F_{mq_1-1}$ は, 補題により $F_{mq_1}$ と互いに素だから, $F_m$ と互いに素でなければならない. また, 補題により, $F_m$ は $F_{mq_1}$ を割り切る. よって, \[ (F_n,\ F_m) = (F_m,\ F_{r_1}).\] これを繰り返すと, \[ (F_n,\ F_m) = (F_{r_{\ell -2}},\ F_{r_{\ell -1}}).\] さらに, $r_{\ell -2} = r_{\ell -1}q_{\ell}$ から (2) により $F_{r_{\ell -2}}$ は $F_{r_{\ell -1}}$ で割り切れるから, \[ (F_n,\ F_m) = F_{r_{\ell -1}} = F_{(m,\ n)}.\]
(2)
$m = 0,$ $m = 1$ のとき, 明らかに成り立つ. そこで, $m > 1$ とする. 補題で $(\Leftarrow )$ は示したから, $(\Rightarrow )$ を示せば良い. $F_m$ が $F_n$ を割り切るとき, (1) により \[ F_m = (F_m,\ F_n) = F_{(m,\ n)}.\] このとき, Fibonacci 数列の単調増加性により $m = (m,\ n)$ となるから, $m$ は $n$ を割り切る. $(\Rightarrow )$ が示された.
(3)
$4$ でない非負整数 $n$ に対して, $n$ が素数でないならば $F_n$ は素数でないことを示す. $F_0 = 0,$ $F_1 = 1$ は素数でないから, $n$ を $0,$ $1,$ $4$ でも素数でない非負整数とする. このとき, $2$ より大きい整数 $\ell,$ $m$ を用いて $n = \ell m$ と書ける. (2) により, $F_n = F_{\ell m}$ は $F_\ell$ で割り切れる. また, Fibonacci 数列の単調増加性より $1 = F_2 < F_\ell < F_n.$ よって, $F_n$ は $1$ でも $F_n$ でもない正の約数 $F_\ell$ を持つから, 素数でない. ゆえに, 対偶は真だから, 示すべき命題も真である.
(4)
($\Leftarrow$)
$m$ が $n$ を割り切るとすると, $F_m$ は $F_n$ を割り切るから, $F_m$ の約数 $\mu$ は $F_n$ を割り切る.
($\Rightarrow$)
$\mu$ が $F_n$ を割り切るとすると, $\mu$ は \[ (F_m,\ F_n) = F_{(m,\ n)}\] を割り切るから, $F_{(m,\ n)} \leqq F_m$ と $m$ の最小性より $(m,\ n) = m$ となり, $m$ は $n$ を割り切る.
後半は, $2,$ $3,$ $5,$ $7,$ $11,$ $13$ で割り切れるような最小の Fibonacci 数がそれぞれ \begin{align*} F_3 &= 2, &\ F_4 &= 3, & F_5 &= 5, \\ F_8 &= 21, & F_{10} &= 55, & F_7 &= 13 \end{align*} であることから従う.

注意

  • (3) の逆は成り立たない. 例えば, $19$ は素数だが, \[ F_{19} = 4181 = 37\cdot 113\] は素数でない. $F_{31},$ $F_{37},$ $F_{41},$ $F_{59},$ $F_{61},$ $F_{67},$ $F_{71},$ $F_{73},$ $F_{79},$ $F_{89},$ $F_{97}$ も素数でない.
  • Fibonacci 数である素数が無限に存在するか否かは未解決である($2013$ 年現在).
  • (2) の (1) を使わない証明については, こちらを参照.

定理≪Lucas 数の整除関係≫

 $2$ 以上の整数 $m,$ $n$ に対して,
(a)
$L_m$ は $L_n$ を割り切る $\iff$ $n$ は $m$ の奇数倍である.
(b)
$L_n$ は $3$ の倍数である $\iff$ $n \equiv 2 \pmod 4.$
 Lucas 数の偶奇性の判定法は, (a) から得られないので, 個別に調べる.

定理≪Lucas 数の偶奇性≫

 任意の非負整数 $n$ に対して,
$L_n$ は偶数 $\iff$ $n$ は $3$ の倍数.

証明

 非負整数 $q$ に対して $L_{3q} \equiv 0,$ $L_{3q+1} \equiv L_{3q+2} \equiv 1 \pmod 2$ を示す.
(i)
$q = 0$ のとき, Lucas 数列の初期条件より主張が成り立つ.
(ii)
与えられた非負整数 $q$ に対して主張が成り立つとすると, $2$ を法として \begin{align*} L_{3q+3} &= L_{3q+1}+L_{3q+2} \equiv 1+1 \equiv 0, \\ L_{3q+4} &= L_{3q+2}+L_{3q+3} \equiv 1+0 \equiv 1, \\ L_{3q+5} &= L_{3q+3}+L_{3q+4} \equiv 0+1 \equiv 1 \end{align*} となり, $q+1$ に対して主張が成り立つ.
(i), (ii) より, 任意の非負整数 $q$ に対して主張が成り立つ.

定理≪$n$ の倍数の Fibonacci 数の存在≫

 任意の正整数 $n$ に対して, $1$ 番目から $n^2$ 番目までの Fibonacci 数の中に $n$ の倍数が存在する.

証明

 整数 $a$ を $n$ で割った余りを $\bar n$ で表す. $n^2+1$ 個の整数の対 $(\overline{F_1},\ \overline{F_2}),$ $\cdots,$ $(\overline{F_{n^2}},\ \overline{F_{n^2+1}}),$ $(\overline{F_{n^2+1}},\ \overline{F_{n^2+2}})$ は最大 $n^2$ 個の値しかとらないから, 鳩の巣原理により, $1 \leqq \ell < m$ なるある整数 $\ell,$ $m$ に対して $(\overline{F_\ell},\ \overline{F_{\ell +1}}) = (\overline{F_m},\ \overline{F_{m+1}})$ となる. つまり, \[ F_\ell \equiv F_m, \quad F_{\ell +1} \equiv F_{m+1} \pmod n.\] $\ell > 1$ のとき, \begin{align*} F_{\ell -1} &= F_{\ell +1}-F_\ell \\ &\equiv F_{m+1}-F_m = F_{m-1} \pmod n. \end{align*} この操作を繰り返すと, \[ F_1 \equiv F_{m-\ell +1}, \quad F_2 \equiv F_{m-\ell +2} \pmod n\] となる. よって, \begin{align*} F_{m-\ell} &= F_{m-\ell +2}-F_{m-\ell +1} \\ &\equiv F_2-F_1 = 1-1 = 0 \pmod n. \end{align*} したがって, $F_{m-\ell}$ は $n$ で割り切れる. $1 \leqq m-\ell \leqq n^2$ だから, 題意が示された.

等式

定理≪Fibonacci 数の和, Lucas, 1876≫

 任意の正整数 $n$ に対して,
(a)
$\sum _{k = 1}^nF_k = F_{n+2}-1.$ 
(b)
$\sum _{k = 1}^nF_{2k-1} = F_{2n}.$ 
(c)
$\sum _{k = 1}^nF_{2k} = F_{2n+1}-1.$ 

証明

(a)
$F_k+F_{k+1} = F_{k+2}$ の辺々を加えると, \[\sum _{k = 0}^nF_k+\sum _{k = 0}^nF_{k+1} = \sum _{k = 0}^nF_{k+2}\] より, \begin{align*} \sum _{k = 0}^nF_k+\sum _{k = 1}^{n+1}F_k &= \sum _{k = 2}^{n+2}F_k \\ &= F_{n+2}+\sum _{k = 1}^{n+1}F_k-F_1. \end{align*} 両辺から $\sum _{k = 0}^nF_{k+1}$ を引くと, 求める等式が得られる.
(b)
(i)
$F_1 = F_2 = 1$ により, $n = 1$ のとき成り立つ.
(ii)
与えられた正整数 $n$ に対して題意が成り立つとすると, \begin{align*} &\sum _{k = 1}^nF_{2k-1}+F_{2k+1} = F_{2n}+F_{2n+1} \\ &= F_{2n+2} = F_{2(n+1)} \end{align*} となり, $n+1$ に対して題意が成り立つ.
(i), (ii) より, 任意の正整数 $n$ に対して, 題意が成り立つ.
(c)
(i)
$F_2 = F_3-1 = 1$ により, $n = 1$ のとき成り立つ.
(ii)
与えられた正整数 $n$ に対して題意が成り立つとすると, \begin{align*} &\sum _{k = 1}^nF_{2k}+F_{2k+2} = F_{2n+1}-1+F_{2n+2} \\ &= F_{2n+3}-1 = F_{2(n+1)+1}-1 \end{align*} となり, $n+1$ に対して題意が成り立つ.
(i), (ii) より, 任意の正整数 $n$ に対して, 題意が成り立つ.

定理≪隣接 Fibonacci 数の積の和≫

 任意の正整数 $n$ に対して,
(a)
$\sum _{k = 1}^{2n-1}F_kF_{k+1} = F_{2n}{}^2.$ 
(b)
$\sum _{k = 1}^{2n}F_kF_{k+1}+1 = F_{2n+1}{}^2.$ 

証明

(a)
(i)
$F_1F_2 = 1\cdot 1 = 1,$ $F_2{}^2 = 1^2 = 1$ は一致するから, $n = 1$ のとき題意が成り立つ.
(ii)
与えられた正整数に対して題意が成り立つとすると, \begin{align*} &\sum _{k = 1}^{2n-1}F_kF_{k+1}+F_{2n}F_{2n+1}+F_{2n+1}F_{2n+2} \\ &= F_{2n}{}^2+F_{2n}F_{2n+1}+F_{2n+1}F_{2n+2} \\ &= F_{2n}(F_{2n}+F_{2n+1})+F_{2n+1}F_{2n+2} \\ &= F_{2n}F_{2n+2}+F_{2n+1}F_{2n+2} \\ &= (F_{2n}+F_{2n+1})F_{2n+2} \\ &= F_{2n+2}{}^2 \end{align*} となり, $n+1$ に対して題意が成り立つ.
(i), (ii) より, 任意の正整数 $n$ に対して題意が成り立つ.
(b)
(i)
$F_1F_2+F_2F_3 = 1\cdot 1+1\cdot 2 = 3,$ $F_3{}^2-1 = 2^2-1 = 3$ は一致するから, $n = 1$ のとき題意が成り立つ.
(ii)
与えられた正整数に対して題意が成り立つとすると, \begin{align*} &\sum _{k = 1}^{2n}F_kF_{k+1}+F_{2n+1}F_{2n+2}+F_{2n+2}F_{2n+3} \\ &= F_{2n+1}{}^2-1+F_{2n+1}F_{2n+2}+F_{2n+2}F_{2n+3} \\ &= F_{2n+1}(F_{2n+1}+F_{2n+2})+F_{2n+2}F_{2n+3}-1 \\ &= F_{2n+1}F_{2n+3}+F_{2n+2}F_{2n+3}-1 \\ &= (F_{2n+1}+F_{2n+2})F_{2n+3}-1 \\ &= F_{2n+3}{}^2-1 \end{align*} となり, $n+1$ に対して題意が成り立つ.
(i), (ii) より, 任意の正整数 $n$ に対して題意が成り立つ.

注意

 実は, 等式 (a), (b) の両辺は, $2n-1$ 番目, $2n$ 番目の黄金長方形の面積を表している.

定理≪隣接 Fibonacci 数の平方和・平方差, Lucas, 1876≫

 任意の非負整数 $n$ に対して,
(a)
$F_n{}^2+F_{n+1}{}^2 = F_{2n+1}.$ 
(b)
$F_{n+2}{}^2-F_{n+1}{}^2 = F_nF_{n+3}.$

証明

(a)
Carlitz の加法定理により, \begin{align*} F_{2n+1} &= F_{n+n+1} \\ &= F_n{}^2+F_{n+1}{}^2. \end{align*}
(b)
Fibonacci 数列の漸化式により, \begin{align*} F_{n+2}{}^2-F_{n+1}{}^2 &= (F_{n+2}-F_{n+1})(F_{n+2}+F_{n+1}) \\ &= F_nF_{n+3}. \end{align*}

定理≪Cassini の公式, 1680≫

 任意の非負整数 $n$ に対して, $F_nF_{n+2}-F_{n+1}{}^2 = (-1)^{n+1}.$

証明

(i)
$F_0F_2-F_1 = 0\cdot 1-1 = -1 = (-1)^2$ だから, $n = 0$ のとき題意が成り立つ.
(ii)
与えられた非負整数 $n$ に対して題意が成り立つとすると, \begin{align*} &F_{n+1}F_{n+3}-F_{n+2}{}^2 \\ &= (F_{n+2}-F_n)(F_{n+1}+F_{n+2})-F_{n+2}{}^2 \\ &= F_{n+2}F_{n+1}-F_nF_{n+1}-F_nF_{n+2} \\ &= F_{n+2}F_{n+1}-F_nF_{n+1}-F_{n+1}{}^2-(-1)^{n+1} \\ &= F_{n+2}F_{n+1}-(F_n+F_{n+1})F_{n+1}-(-1)^{n+1} \\ &= F_{n+2}F_{n+1}-F_{n+2}F_{n+1}+(-1)^{n+2} \\ &= (-1)^{n+2} \end{align*} となり, $n+1$ に対して題意が成り立つ.
(i), (ii) より, 任意の非負整数 $n$ に対して題意が成り立つ.

定理≪Schub の公式, 1950≫

 任意の非負整数 $n$ に対して, \[ 5F_n{}^2+4(-1)^n = L_n{}^2.\]

証明

(i)
$5F_0{}^2+4 = 4 = L_0{}^2$ より, $n = 0$ のとき成り立つ.
(ii)
$n > 0$ のとき, Fibonacci 数列と Lucas 数の相互関係, Cassini の公式により, \begin{align*} &L_n{}^2-4(F_n{}^2+(-1)^n) \\ &= (F_{n+1}+F_{n-1})^2-4F_{n+1}F_{n-1} \\ &= (F_{n+1}-F_{n-1})^2 = F_n{}^2 \end{align*} となるから, $5F_n{}^2+4(-1)^n = L_n{}^2.$
 この等式は, 正整数が Fibonacci 数であるための必要十分条件を与える. 詳しくは, こちらを参照.

その他

定理≪Fibonacci 数の判定法, Gessel, 1972≫

 任意の非負整数 $\nu$ に対して,
$\nu$ は Fibonacci 数 $\iff$ $5\nu ^2+4$ または $5\nu ^2-4$ は平方数.

証明: $(\Leftarrow )$ には代数的整数論の知識を用いる.

$(\Rightarrow )$
Schub の公式から従う.
$(\Leftarrow )$
$5\cdot 0+4 = 2^2$ は平方数であり, $0 = F_0$ は Fibonacci 数だから, $\nu > 0$ とする. $5\nu ^2\pm 4$ が平方数であるとする. このとき, ある非負整数 $\mu$ を用いて \[ 5\nu ^2\pm 4 = \mu ^2 \quad \cdots [1]\] と書ける. $\mu ^2-5\nu ^2 = \pm 4$ だから, \[\frac{\mu +\nu\sqrt 5}{2}\cdot\frac{\mu -\nu\sqrt 5}{2} = \pm 1 \quad \cdots [2].\] $[1]$ より, $\mu ^2 \equiv \nu ^2 \pmod 2$ だから, $\mu$ と $\nu$ の偶奇は一致しなければならない. よって, $a = \dfrac{\mu +\nu\sqrt 5}{2}$ は $K = \mathbb Q(\sqrt 5)$ の整数環 $O_K$ に属する. さらに, $[2]$ より $a$ のノルムは $\pm 1$ だから, $a$ は $O_K$ の単数である. $O_K$ の単数は $\pm\alpha ^n$ $(n \in \mathbb Z)$ の形の整数に限るが, $\nu > 0$ より $a > 1$ であり, $\alpha > 1$ だから, ある正整数 $n$ について $a = \alpha ^n$ となる. よって, Binet の公式により, \[ a = \frac{(\alpha ^n+\beta ^n)+(\alpha ^n-\beta ^n)}{2} = \frac{L_n+F_n\sqrt 5}{2}.\] $1,$ $\sqrt 5$ は $\mathbb Q$ 上線形独立だから, 両辺の $\sqrt 5$ の係数を比較すると, $\nu = F_n.$

定理≪Fibonacci 数による整数の分割≫

 任意の非負整数 $n$ は, 互いに隣り合わない Fibonacci 数の和として表せる.

証明

(i)
$0 = F_0$ だから, $n = 0$ のとき題意が成り立つ.
(ii)
与えられた正整数 $n$ について, $n$ 未満の任意の非負整数に対して題意が成り立つとする. $F_0 = 0,$ $F_1 = F_2 = 1,$ $F_3 = 2$ に注意すると, $F_m \leqq n < F_{m+1}$ を満たす番号 $m \geqq 2$ が存在する.
  • $F_m = n$ のとき, $n$ は Fibonacci 数そのものである.
  • $F_m < n$ のとき, $n-F_m < n$ だから, 帰納法の仮定により $S = n-F_m$ は互いに隣り合わない Fibonacci 数の和として表せるが, $n-F_m < F_{m+1}-F_m = F_{m-1}$ だからそれらの Fibonacci 数は $m-2$ 番目までの Fibonacci 数である. よって, $n = S+F_m$ は互いに隣り合わない複数の Fibonacci 数の和として表せる.
(i), (ii) より, 任意の非負整数に対して題意が成り立つ.

注意

 Fibonacci 数 $F$ そのものを $1$ 個の Fibonacci 数の和 $\sum\limits_{k = 1}^1F$ とみなした.

定理≪累乗数の Fibonacci 数, Bugeaud-Mignotte-Siksek, 2004≫

 累乗数である Fibonacci 数は $F_0 = 0^2,$ $F_1 = F_2 = 1^2,$ $F_6 = 2^3,$ $F_{12} = 12^2$ に限る.

注意

 平方数である Fibonacci 数が $F_0,$ $F_1 = F_2,$ $F_{12}$ に限ることは 1964 年の Cohn の論文で証明され, 立方数である Fibonacci 数が $F_0,$ $F_1 = F_2,$ $F_6$ に限ることは 1969 年の London-Finkelstein の論文で証明された.
 ここでは, 平方数の Fibonacci 数を決定する. 証明には, Jacobi 記号の性質を使う.

定義≪Legendre 記号・Jacobi 記号≫

(1)
$p$ を素数, $a$ を $p$ と互いに素な整数とする. $x^2 \equiv a \pmod p$ が整数解 $x$ を持つとき $\left(\dfrac{a}{p}\right) = 1,$ 整数解を持たないとき $\left(\dfrac{a}{p}\right) = -1$ と定める.
(2)
$a,$ $b$ を互いに素な整数とする. $b$ の素因数分解が $b = p_1{}^{e_1}\cdots p_r{}^{e_r}$ ($p_1,$ $\cdots,$ $p_r$: 相異なる素数)であるとき, \[\left(\frac{a}{b}\right) = \left(\frac{a}{p_1}\right) ^{e_1}\cdots\left(\frac{a}{p_r}\right) ^{e_r}\] と定める.

補題≪Jacobi 記号の性質≫

 $a,$ $b$ を整数とする.
(a)
$a,$ $b$ を互いに素な整数とする. $x^2 \equiv a \pmod b$ の整数解 $x$ が存在するならば, $\left(\dfrac{a}{b}\right) = 1.$ すなわち, $\left(\dfrac{a}{b}\right) = -1$ ならば, $x^2 \equiv a \pmod b$ の整数解 $x$ は存在しない.
(b)
$b$ が正の奇数であるとき, \[\left(\frac{-1}{b}\right) = (-1)^{\frac{b-1}{2}}.\]

証明

(a)
$x^2 \equiv a \pmod b$ の整数解 $x$ の存在を仮定する. また, $b$ の素因数分解が $b = p_1{}^{e_1}\cdots p_r{}^{e_r}$ ($p_1,$ $\cdots,$ $p_r$: 相異なる素数)であるとする. このとき, $x^2-a$ は $b$ の倍数だから, 各番号 $i$ に対して $x^2-a$ は $p_i$ の倍数であり, $x^2 \equiv a \pmod{p_i}$ から $\left(\dfrac{a}{p_i}\right) = 1$ となる. よって, \[\left(\frac{a}{b}\right) = \left(\frac{a}{p_1}\right) ^{e_1}\cdots\left(\frac{a}{p_r}\right) ^{e_r} = 1^{e_1}\cdots 1^{e_r} = 1.\]
(b)
(i)
$b$ が素数 $p$ のとき. $p$ 元体 $\mathbb F_p$ の乗法群 $\mathbb F_p{}^\times = \mathbb F_p\setminus\{ 0\}$ が位数 $p-1$ の巡回群である. その生成元を $\zeta$ とする. $x \equiv -1 \pmod p$ を満たす整数 $x$ が存在すれば, $x \pmod p = \zeta ^{(p-1)/4}$ と表せる. $\mathbb F_p{}^\times$ にこのような元が存在するためには, $p \equiv 1 \pmod 4$ であることが必要十分である.
(ii)
一般の場合. (i) と奇素数 $p,$ $q$ に対して \[ (p-1)(q-1) \equiv 0 \pmod 4\] より \[ pq-1 \equiv (p-1)+(q-1) \pmod 4\] であることから従う.
 さらに, 証明で使う補題を証明する.

補題≪$n$ 番目の Fibonacci 数と Lucas 数の最大公約数≫

 任意の非負整数 $n$ に対して, $F_n,$ $L_n$ の最大公約数は $1$ または $2$ の累乗に限る.

証明

 $F_0 = 0,$ $L_0 = 2$ の最大公約数は $2.$ そこで, $n > 0$ とする. $F_n,$ $L_n$ の共通の素因数 $p$ が存在したとする. このとき, Fibonacci 数列と Lucas 数列の相互関係により \[ L_n = F_{n-1}+F_{n+1} = 2F_{n-1}+F_n\] となるから, \begin{align*} 2F_{n-1} \equiv 0 \pmod p. \end{align*} $F_{n-1}$ は $F_n$ と互いに素であり, したがって $F_{n-1}$ は $p$ で割り切れないから, $p = 2.$ ゆえに, $F_n,$ $L_n$ の最大公約数は, $1$ でないとき, $2$ の累乗である. 題意が示された.

補題≪Fibonacci 数・Lucas 数の合同式≫

 任意の非負整数 $q,$ $r,$ $m,$ $n$ に対して,
(a)
$n = 4\cdot 3^ij$ ($i,$ $j$: 非負整数, $j$ は $3$ で割り切れない)のとき, \begin{align*} F_{m+n} &\equiv -F_m \pmod{L_{2j}}, \\ L_{m+n} &\equiv -L_m \pmod{L_{2j}}. \end{align*}
(b)
非負整数 $j$ が $3$ で割り切れないとき, \[ L_{2j} \equiv 3 \pmod 4.\]
(c)
\[ L_{12q+r} \equiv L_r \pmod 8.\]

証明

(a)
$i = 0$ のとき. Ferns の加法定理により, \begin{align*} 2F_{m+n} &= F_mL_n+L_mF_n \\ &= F_m(L_{2j}{}^2-2)+L_mF_{2j}L_{2j}+ \\ &\equiv -2F_m \pmod{L_{2j}}, \\ 2L_{m+n} &= 5F_mF_n+L_mL_n \\ &= 5F_mF_{2j}L_{2j}+L_m(L_{2j}{}^2-2) \\ &\equiv -2L_m \pmod{L_{2j}}. \end{align*} $j$ は $3$ の倍数でないから, $L_j$ は偶数でない. よって, \begin{align*} F_{m+n} &\equiv -F_m \pmod{L_{2j}}, \\ L_{m+n} &\equiv -L_m \pmod{L_{2j}}. \end{align*} さらに, \begin{align*} F_{m+12j} &= F_{m+4j+4j+4j} \equiv -F_{m+4j+4j} \\ &\equiv F_{m+4j} \equiv -F_m \pmod{L_{2j}}, \\ L_{m+12j} &= L_{m+4j+4j+4j} \equiv -L_{m+4j+4j} \\ &\equiv L_{m+4j} \equiv -L_m \pmod{L_{2j}}. \end{align*} これを繰り返すと, 任意の非負整数 $i$ に対して与式の成り立つことが分かる.
(b)
$j$ が $3$ で割り切れないことより $L_j$ は奇数だから, \begin{align*} L_{2j} &= L_j{}^2+2(-1)^{j+1} \\ &\equiv 1+2(-1)^{j+1} \equiv 3 \pmod 4. \end{align*}
(c)
$L_{r+12} \equiv L_r \pmod 8$ を示せば良い. Ferns の加法定理により \begin{align*} 2L_{r+12} &= 5F_rF_{12}+L_rL_{12} \\ &= 5\cdot 144 F_r+322L_r \end{align*} となるから, \[ L_{r+12} = 360F_r+161 L_r \equiv L_r \pmod 8.\]

補題≪平方数の Lucas 数≫

 平方数である Lucas 数は $L_1 = 1^2,$ $L_3 = 2^2$ に限る.

証明: Jacobi 記号の性質を利用

(I)
$n = 2m$ ($m$: 非負整数)のとき. \[ L_n = L_{2m} = L_m{}^2+2(-1)^{m+1}.\] $L_m{}^2$ を $4$ で割った余りは $0$ または $1$ であり, $L_n$ を $4$ で割った余りは $0$ または $1$ にならないから, $L_n$ は平方数でない.
(II)
$n$ が奇数のとき.
(i)
$n = 1$ のとき. $L_1 = 1^2$ は平方数である.
(ii)
$n = 4\cdot 3^ij+1$ ($i,$ $j$: 非負整数, $j$ は $3$ で割り切れない)のとき. 前補題により, \[ L_n \equiv -L_1 = -1 \pmod{L_{2j}}\] となる. よって, Jacobi 記号の計算 \begin{align*} \left(\frac{-1}{L_{2j}}\right) = (-1)^{\frac{L_{2j}-1}{2}} = -1 \\ \quad (\because L_{2j} \equiv 3 \pmod 4) \end{align*} により, $L_n$ は平方数でない.
(iii)
$n = 3$ のとき. $L_3 = 2^2$ は平方数である.
(iv)
$n = 4\cdot 3^ij+3$ ($i,$ $j$: 非負整数, $j$ は $3$ で割り切れない)のとき. 前補題により, \[ L_n \equiv -L_3 = -4 \pmod{L_{2j}}\] となる. よって, \[\left(\frac{-4}{L_{2j}}\right) = \left(\frac{-1}{L_{2j}}\right) = -1\] により, $L_n$ は平方数でない.
ゆえに, $n \in \{ 1,\ 3\}.$

補題≪平方数の $2$ 倍の Lucas 数≫

 平方数の $2$ 倍の形をした Lucas 数は $L_0 = 2\cdot 1^2,$ $L_6 = 2\cdot 3^2$ に限る.

証明: Jacobi 記号の性質を利用

 $L_n = 2a^2$ ($a$: 整数)と表されるとする. このとき, $a^2$ を $8$ で割った余りは $0$ または $1$ だから $L_n$ を $8$ で割った余りは $0$ または $2$ であり, $L_n$ は偶数だから $n$ は $3$ の倍数である.
(I)
$n$ が偶数のとき.
(i)
$n = 0$ のとき. $L_0 = 2\cdot 1^2$ は平方数の $2$ 倍である.
(ii)
$n = 4\cdot 3^ij$ ($i,$ $j$: 非負整数, $j$ は $3$ で割り切れない)のとき. 前補題により, \[ 2L_n \equiv -2L_0 = -4 \pmod{L_{2j}}\] となる. よって, Jacobi 記号の計算 \begin{align*} \left(\frac{-4}{L_{2j}}\right) = \left(\frac{-1}{L_{2j}}\right) = (-1)^{\frac{L_{2j}-1}{2}} = -1 \\ (\because L_{2j} \equiv 3 \pmod 4) \end{align*} により, $2L_n$ は平方数でない. したがって, $L_n$ は平方数の $2$ 倍でない.
(iii)
$n = 2$ のとき. $L_2 = 3$ は平方数の $2$ 倍でない.
(iv)
$n = 6$ のとき. $L_6 = 2\cdot 3^2$ は平方数の $2$ 倍である.
(v)
$n = 4\cdot 3^ij+6$ ($i,$ $j$: 非負整数, $j$ は $3$ で割り切れない)のとき. 前補題により, \[ 2L_n \equiv -2L_6 = -36 \pmod{L_{2j}}\] となる. よって, \[\left(\frac{-36}{L_{2j}}\right) = \left(\frac{-1}{L_{2j}}\right) = -1\] により, $2L_n$ は平方数でない. したがって, $L_n$ は平方数の $2$ 倍でない.
(II)
$n$ が奇数のとき. $n$ を $12$ で割った商を $q,$ 余りを $r$ とおく. このとき, $r \in \{ 3,\ 9\}.$
(i)
$r = 3$ のとき. \[ L_n = L_{12q+3} \equiv L_3 = 4 \pmod 8.\] これは $L_n$ を $8$ で割った余りが $0$ または $2$ であることに反する.
(ii)
$r = 9$ のとき. \[ L_n = L_{12q+9} \equiv L_9 = 76 \equiv 4 \pmod 8.\] これは $L_n$ を $8$ で割った余りが $0$ または $2$ であることに反する.
ゆえに, $n \in \{ 0,\ 6\}.$

定理≪平方数の Fibonacci 数≫

 平方数である Fibonacci 数は $F_0 = 0^2,$ $F_1 = F_2 = 1^2,$ $F_{12} = 12^2$ に限る.

証明: Jacobi 記号の性質を利用

 $F_n$ が平方数であるとする.
(I)
$n$ が偶数のとき. $m = n/2$ とおく. \[ F_n = F_{2m} = F_mL_m.\] $F_m,$ $L_m$ の最大公約数は $1$ か $2$ の累乗だから, 次の $2$ つの場合のみが起こる.
(i)
$F_m,$ $L_m$ が平方数の場合. このとき, 前補題により $m \in \{ 1,\ 3\}$ となる. $F_1 = 1^2$ は平方数だから $m = 1$ は条件を満たし, $F_3 = 2$ は平方数でないから $m = 3$ は条件を満たさない. よって, $n = 2.$
(ii)
$F_m,$ $L_m$ が平方数の $2$ 倍の場合. このとき, 前補題により $m \in \{ 0,\ 6\}$ となる. $F_0 = 2\cdot 0^2,$ $F_6 = 2\cdot 2^2$ だから, $m = 0,$ $m = 6$ は条件を満たす. よって, $n \in \{ 0,\ 12\}.$
(II)
$n$ が奇数のとき.
(i)
$n = 1$ のとき. $F_1 = 1^2$ は平方数である.
(ii)
$n = 4\cdot 3^ij+1$ ($i,$ $j$: 非負整数, $j$ は $3$ で割り切れない)のとき. 前補題により, \[ F_n \equiv -F_1 = -1 \pmod{L_{2j}}\] となる. よって, Jacobi 記号の計算 \begin{align*} \left(\frac{-1}{L_{2j}}\right) = (-1)^{\frac{L_{2j}-1}{2}} = -1 \\ (\because L_{2j} \equiv 3 \pmod 4) \end{align*} により, $F_n$ は平方数でない.
(iii)
$n = 4\cdot 3^ij+3$ ($i,$ $j$: 非負整数, $j$ は $3$ で割り切れない)のとき. (ii) の場合に帰着される.
ゆえに, $n \in \{ 0,\ 1,\ 2,\ 12\}.$

参考文献

  • T. Koshy, "Fibonacci and Lucas Numbers with Applications," Pure and Applied Mathematics, John Wiley, New York, 2001.
  • S. Vajda, "Fibonacci and Lucas Numbers, and the Golden Section," Theory and Applications, Ellis Horwood, Chichester, 1989.

問題

数学 B: 数列

問題≪階段の上り方とフィボナッチ数列≫

 $1$ 歩目は $1$ 段だけ上るとし, $2$ 歩目以降は $1$ 歩で $1$ 段上ることも $2$ 段上ることもできるとして, $n$ 段の階段を上る方法の総数を $F_n$ とおく.
(1)
$F_{n+2} = F_n+F_{n+1}$ が成り立つことを示せ.
(2)
数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列となるような定数 $\alpha,$ $\beta$ の組を $1$ つ求めよ.
(3)
$F_n$ を $n$ の式で表せ.

解答例

(1)
$n+2$ 段の階段を上るとき, 最後の $1$ 歩に着目すると, 次の $2$ つの場合が考えられる.
(i)
最後の $1$ 歩で $2$ 段上る場合. $n+2$ 段を上る方法は, $n$ 段の上り方 $F_n$ 通りだけある.
(ii)
最後の $1$ 歩で $1$ 段上る場合. $n+2$ 段を上る方法は, $n+1$ 段の上り方 $F_{n+1}$ 通りだけある.
(i), (ii) は排反だから, \[ F_{n+2} = F_n+F_{n+1} \quad \cdots [1]\] が成り立つ.
(2)
数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列であるとき, \begin{align*} F_{n+2}-\alpha F_{n+1} &= \beta (F_{n+1}-\alpha F_n), \\ F_{n+2}-\beta F_{n+1} &= \alpha (F_{n+1}-\beta F_n) \end{align*} から \[ F_{n+2} = (\alpha +\beta )F_{n+1}-\alpha\beta F_n \quad \cdots [2]\] が成り立つ. $[1],$ $[2]$ から, \[\alpha +\beta = 1,\quad \alpha\beta = -1\] が成り立てば良い. このとき, $\alpha,$ $\beta$ は $2$ 次方程式 $x^2-x-1 = 0$ の解だから, 条件を満たす $\alpha,$ $\beta$ として \[\alpha = \frac{1-\sqrt 5}{2}, \quad \beta = \frac{1+\sqrt 5}{2}\] がとれる.
(3)
明らかに $F_1 = 1$ であり, $1$ 歩目は $1$ 段だけ上るという条件から $F_2 = 1$ である. 数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ の初項はそれぞれ, \begin{align*} F_2-\alpha F_1 = 1-\alpha &= \frac{1+\sqrt 5}{2} = \beta, \\ F_2-\beta F_1 = 1-\beta &= \frac{1-\sqrt 5}{2} = \alpha \end{align*} である. よって, $\alpha,$ $\beta$ の取り方から, \begin{align*} F_{n+1}-\alpha F_n &= \beta ^n, \\ F_{n+1}-\beta F_n &= \alpha ^n \end{align*} が成り立つ. 辺々を引くと \[ (\beta -\alpha )F_n = \beta ^n-\alpha ^n\] となるので, $\beta -\alpha = \sqrt 5$ から \[ F_n = \frac{1}{\sqrt 5}\left\{\left(\frac{1+\sqrt 5}{2}\right) ^n-\left(\frac{1-\sqrt 5}{2}\right) ^n\right\}\] が成り立つ.

数学 B: 数列

問題≪ラメの定理≫

 $a,$ $b$ を $a > b \geqq 1$ なる整数とし, ユークリッドの互除法の計算 \begin{align*} a &= bq_1+r_1, \quad 0 < r_1 < b, \\ b &= r_1q_2+r_2, \quad 0 < r_2 < r_1, \\ &\ \,\vdots \\ r_{l-2} &= r_{l-1}q_l+r_l, \quad 0 = r_l < r_{l-1} \end{align*} により整数 $l$ と $q_1,$ $\cdots,$ $q_l,$ $r_1,$ $\cdots,$ $r_l$ を定める. また, 数列 $\{ F_n\}$ を \[ F_1 = F_2 = 1, \quad F_{n+2} = F_n+F_{n+1}\] で定め, $\alpha$ を $x^2 = x+1$ の正の解とする.
(1)
$b \geqq F_{l+1}$ が成り立つことを示せ.
(2)
$F_{n+1} \geqq \alpha ^{n-1}$ が成り立つことを示せ.
(3)
$\alpha ^5 > 10$ であることを示せ.
(4)
$l \leqq 5\log_{10}b$ が成り立つことを示せ.

解答例

(1)
与式から \begin{align*} b &\geqq r_1+r_2, \\ &\ \,\vdots \\ r_{k-2} &\geqq r_{k-1}+r_k \quad (2 < k < l), \\ &\ \,\vdots \\ r_{l-2} &> r_{l-1} > r_l = 0 \end{align*} が成り立つので, $r_{l-1} = 1,$ $r_{l-2} = 2,$ $\cdots,$ $r_{k-2} = r_{k-1}+r_k,$ $\cdots,$ $b = r_1+r_2$ のとき, つまり $b = F_{l+1}$ のとき $b$ は最小となる. よって, $b \geqq F_{l+1}$ である.
(2)
(i)
$n = 1$ のとき, $F_2 = 1$ から, $F_{n+1} \geqq \alpha ^{n-1}$ が成り立つ.
$n = 2$ のとき, $F_3 = 2 > \dfrac{1+\sqrt 5}{2} = \alpha$ から, $F_{n+1} \geqq \alpha ^{n-1}$ が成り立つ.
(ii)
与えられた正の整数 $n$ に対して $F_{n+1} \geqq \alpha ^{n-1},$ $F_{n+2} \geqq \alpha ^n$ が成り立つとすると, $\alpha ^2 = 1+\alpha$ であるから \begin{align*} F_{n+3} &= F_{n+1}+F_{n+2} \\ &\geqq \alpha ^{n-1}+\alpha ^n = \alpha ^{n-1}(1+\alpha ) \\ &= \alpha ^{n-1}\alpha ^2 = \alpha ^{n+1} \end{align*} となる.
(i), (ii) から, すべての正の整数 $n$ に対して $F_{n+1} \geqq \alpha ^{n-1}$ が成り立つ.
(3)
$\alpha = \dfrac{1+\sqrt 5}{2}$ であるから, $(1+\sqrt 5)^5 > 10\cdot 2^5 = 320$ を示せばよい. \begin{align*} (1+\sqrt 5)^5 &= \{ (1+\sqrt 5)^2\} ^2(1+\sqrt 5) \\ &= (6+2\sqrt 5)^2(1+\sqrt 5) \\ &= (56+24\sqrt 5)(1+\sqrt 5) \\ &= 176+80\sqrt 5 \end{align*} であるから, $80\sqrt 5 > 144$ を示せばよい. これは $(80\sqrt 5)^2 = 32000 > 20736 = 144^2$ から従う.
(4)
$m = \log _{10}b$ とおくと, $b < 10^m$ が成り立つ. これと (1), (2) から, \[\alpha ^{l-1} \leqq F_{l+1} \leqq b < 10^m\] が成り立つ. よって, \[ 10^{l-1} < \alpha ^{5(l-1)} < 10^{5m}\] であるから, $l-1 < 5m$ つまり $l < 5m+1$ が成り立つ. $l$ は整数であるから, $l \leqq 5m = 5\log_{10}b$ が成り立つ.

数学 III: 極限

問題≪フィボナッチ数の逆数和≫

 $F_1 = F_2 = 1,$ $F_{n+2} = F_n+F_{n+1}$ で定まる数列 $\{ F_n\}$ について,
(1)
$F_{2n-1} \geqq 2^{n-1},$ $F_{2n} \geqq 2^{n-1}$ が成り立つことを示せ.
(2)
$\displaystyle\sum_{n = 1}^\infty\frac{1}{F_n}$ は収束することを示せ. ただし, 次の数列の収束判定法を用いてよい: 数列 $\{ a_n\},$ $\{ b_n\}$ について, $0 < a_n \leqq b_n$ であり, $\{ b_n\}$ が収束するならば, $\{ a_n\}$ も収束する.

解答例

(1)
$\{ F_n\}$ は定義より単調増加である. よって, \[ F_{n+2} = F_n+F_{n+1} \geqq 2F_n\] が成り立つので, \begin{align*} F_{2n-1} &\geqq 2^{n-1}F_1 = 2^{n-1}, \\ F_{2n} &\geqq 2^{n-1}F_2 = 2^{n-1} \end{align*} が得られる.
(2)
\begin{align*} \sum_{k = 1}^{2m}\frac{1}{F_k} &= \sum_{k = 1}^m\frac{1}{F_{2k-1}}+\sum_{k = 1}^m\frac{1}{F_{2k}} \\ &\leqq \sum_{k = 1}^m\frac{1}{2^{k-1}}+\sum_{k = 1}^m\frac{1}{2^{k-1}} \\ &= 2\sum_{k = 1}^m\left(\frac{1}{2}\right) ^{k-1} \end{align*} の右辺の等比数列の和は収束するから, $\displaystyle\sum_{n = 1}^\infty\frac{1}{F_n}$ は収束する.