フィボナッチ数列の加法定理
加法定理
定理《フィボナッチ数列・リュカ数列の加法定理》
すべての非負整数 $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)
- $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$ の倍数
証明
こちらを参照.
高校数学の問題
整数の性質
問題《フィボナッチ数列の性質》
$m,$ $n$ を非負整数とする.
\[ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_n+F_{n+1}\]
により定まる数列 $\{ F_n\}$ について,
\[ F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1} \quad \cdots [1]\]
の成り立つことが知られている (こちらを参照).
次のことを示せ.
- (1)
- $0 < m \leqq n$ とする. $m$ が $n$ を割り切るならば, $F_m$ は $F_n$ を割り切る.
- (2)
- $F_n,$ $F_{n+1}$ は互いに素である.
- (3)
- $2 < m \leqq n$ とする. $F_m$ が $F_n$ を割り切るならば, $m$ は $n$ を割り切る.
- (4)
- $n \neq 4$ とする. $F_n$ が素数ならば, $n$ は素数である.
解答例
こちらを参照.
数列
問題《フィボナッチ数列の加法定理と $2$ 倍公式》
$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 [*]$ が成り立つ.
- (2)
- $n \geqq 1$ のとき, $F_{2n} = F_{n+1}{}^2-F_{n-1}{}^2,$ $F_{2n+1} = F_n{}^2+F_{n+1}{}^2$ が成り立つ.
解答例
こちらを参照.