有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

フィボナッチ数列の加法定理

加法定理

定理《フィボナッチ数列・リュカ数列の加法定理》

 すべての非負整数 $m,$ $n$ に対して,
(1)
$F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1}$ (カーリッツ, $1964$ 年)
(2)
$L_{m+n+1} = F_mL_n+F_{m+1}L_{n+1}$ (カーリッツ, $1964$ 年)
(3)
$2F_{m+n} = F_mL_n+L_mF_n$ (ファーンズ, $1967$ 年)
(4)
$2L_{m+n} = 5F_mF_n+L_mL_n$ (ファーンズ, $1967$ 年)
が成り立つ.

証明

 $m$ を固定し, $n$ に関する数学的帰納法で示す.
(1)
(i)
$F_0 = 0,$ $F_1 = F_2 = 1$ から \[\begin{aligned} &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{aligned}\] となるので, $n = 0,$ $1$ のとき (1) が成り立つ.
(ii)
$n = k,$ $k+1$ ($k$: 非負整数)のとき (1) が成り立つことを仮定する. このとき, \[\begin{aligned} &F_{m+k+3} \\ &= F_{m+k+1}+F_{m+k+2} \\ &= F_mF_k+F_{m+1}F_{k+1}+F_mF_{k+1}+F_{m+1}F_{k+2} \\ &= F_m(F_k+F_{k+1})+F_{m+1}(F_{k+1}+F_{k+2}) \\ &= F_mF_{k+2}+F_{m+1}F_{k+3} \end{aligned}\] となり, $n = k+2$ のとき (1) が成り立つ.
(2)
(i)
$L_0 = 2,$ $L_1 = 1,$ $L_2 = 3$ から \[\begin{aligned} &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{aligned}\] となるので, $n = 0,$ $1$ のとき (2) が成り立つ.
(ii)
$n = k,$ $k+1$ ($k$: 非負整数)のとき (2) が成り立つことを仮定する. このとき, \[\begin{aligned} &L_{m+k+3} \\ &= L_{m+k+1}+L_{m+k+2} \\ &= F_mL_k+F_{m+1}L_{k+1}+F_mL_{k+1}+F_{m+1}L_{k+2} \\ &= F_m(L_k+L_{k+1})+F_{m+1}(L_{k+1}+L_{k+2}) \\ &= F_mL_{k+2}+F_{m+1}L_{k+3} \end{aligned}\] となり, $n = k+2$ のとき (2) が成り立つ.
(3)
(i)
$F_0 = 0,$ $F_1 = 1,$ $L_0 = 2,$ $L_1 = 1$ から \[\begin{aligned} &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{aligned}\] となるので, $n = 0,$ $1$ のとき (3) が成り立つ.
(ii)
$n = k,$ $k+1$ ($k$: 非負整数)のとき (3) が成り立つことを仮定する. このとき, \[\begin{aligned} &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{aligned}\] となり, $n = k+2$ のとき (3) が成り立つ.
(4)
(i)
$F_0 = 0,$ $F_1 = 1,$ $L_0 = 2,$ $L_1 = 1$ から \[\begin{aligned} &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{aligned}\] となるので, $n = 0,$ $1$ のとき (4) が成り立つ.
(ii)
$n = k,$ $k+1$ ($k$: 非負整数)のとき (4) が成り立つことを仮定する. このとき, \[\begin{aligned} &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{aligned}\] となり, $n = k+2$ のとき (4) が成り立つ.
以上から, すべての非負整数 $m,$ $n$ に対して (1)~(4) が成り立つ.

整数論

定理《フィボナッチ数の整除関係》

 すべての非負整数 $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$ で割り切れるような最小のフィボナッチ数が $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)$ で表した.

証明

 こちらを参照.

問題

数学 A: 整数の性質

問題《フィボナッチ数列の加法定理と性質》

 $m,$ $n$ を非負整数とする. \[ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_n+F_{n+1}\] により定まる数列 $\{ F_n\}$ について, 次のことを示せ.
(1)
$F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1}\ \cdots (P)$ が成り立つ. 
(2)
$0 < m \leqq n$ のとき, $m$ が $n$ を割り切るならば, $F_m$ は $F_n$ を割り切る.
(3)
$F_n,$ $F_{n+1}$ は互いに素である.
(4)
$2 < m \leqq n$ のとき, $F_m$ が $F_n$ を割り切るならば, $m$ は $n$ を割り切る.
(5)
$n \neq 4$ のとき, $F_n$ が素数ならば, $n$ は素数である.

解答例

 こちらを参照.