フィボナッチ数列F(n)(ただし、n=0,1,2…)を次のように定める。 F(0)=0,F(1)=1

フィボナッチ数列F(n)(ただし、n=0,1,2…)を次のように定める。
F(0)=0,F(1)=1,F(n+2)=F(n+1)+Fn
(1)F(n+3),F(n+4),F(n+5)をそれぞれ
aF(n+1)+bF(n)(a,bは整数)
の形で表せ。

(2)一般にF(n+m)(m>=1)はmのみに依存する適当な0以上の整数x,yによって、
F(n+m)=F(x)F(n+1)+FyFn
の形に表されることを示せ。

(3)m>=1,n>=1に対して、mがnの倍数ならば、FmはFnの倍数であることを示せ。


(4)m>=1に対して、Fmが素数ならば、mは素数またはm=4であることを示せ。


フィボナッチ数列に関する問題なのですがよくわかりません。どなたか解説お願いします

No.1 ベストアンサー 回答者： ありものがたり 回答日時： 2019/09/22 19:40

こういう「凝った」問題は、概ね小問の誘導に乗っていくだけです。

(1)
漸化式を繰り返し使って、
F(n+3) = F(n+2) + F(n+1) = { F(n+1) + F(n) } + F(n+1) = 2F(n+1) + F(n),
F(n+4) = F(n+3) + F(n+2) = { 2F(n+1) + F(n) } + { F(n+1) + F(n) } = 3F(n+1) + 2F(n),
F(n+5) = F(n+4) + F(n+3) = { 3F(n+1) + 2F(n) } + { 2F(n+1) + F(n) } = 5F(n+1) + 3F(n).

(2)
(1)の途中計算を見れば、F(n+m) = F(m)F(n+1) + F(m-1)F(n) であることが見えてくるでしょう。
証明は、その考えをそのまま m に関する帰納法の形に書けばよいです。
m = 1 のとき、F(n+1) = 1F(n+1) + 0F(n) = F(1)F(n+1) + F(0)F(n) で成立している。
m ≦ k のとき成立したと仮定すると、F(n+k) = F(k)F(n+1) + F(k-1)F(n),
F(n+k-1) = F(k-1)F(n+1) + F(k-2)F(n) である。これらを使って、
F(n+k+1) = F(n+k) + F(n+k-1) = { F(k)F(n+1) + F(k-1)F(n) } + { F(k-1)F(n+1) + F(k-2)F(n) }
= { F(k) + F(k-1) }F(n+1) + { F(k-1) + F(k-2) }F(n) = F(k+1)F(n+1) + F(k)F(n).
予想は m ≦ k+1 でも成立することになる。
よって、数学的帰納法により、上記の予想は任意の自然数 m について成り立つ。

(3)
これも帰納法ですね。(2)を使い、m = nｊ (ｊは自然数) の j に関する帰納法で示しましょう。
j = 1 のとき、F(m) = F(n) で成立している。
j = k のとき成立したと仮定すると、F(nk) は F(n) の倍数である。
(2)より F(n(k+1)) = F(n+nk) = F(nk)F(n+1) + F(nk-1)F(n) だが、
F(nk) が F(n) の倍数なので F(nk)F(n+1) + F(nk-1)F(n) も F(n) の倍数となる。
j = k+1 でも、F(m) は F(n) の倍数であると判った。
よって、数学的帰納法により、任意の自然数 ｊ について F(m) は F(n) の倍数である。

(4)
(3)より、m が n の倍数であるためには、F(m) が F(n) の倍数であることが必要です。
F(m) が素数であれば、F(m) の約数となる F(n) は F(m) と F(1) = F(2) = 1 に限られます。
m の約数となる n の候補が n = m と n = 1, 2 に限られるということなので、
m は素数または 4 であることが判ります。
2 だけを素因数に持つ合成数 2,4,8,16,… の中で、約数が自分自身と 2,1 だけなのは
4 のみです。

この回答へのお礼

本当に本当にありがとうございます！助かります！！！

お礼日時：2019/09/22 20:25