F0=0, F1=1, Fn+2=Fn+1+Fn
と定義され, 初めの方の値は
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
ところでTAOCPの第1巻に,
F3nは2(=F3)の倍数
F4nは3(=F4)の倍数
F5nは5(=F5)の倍数
FknはFkの倍数
と書いてあった.
たしかにF3, F6, F9は偶数だし,
F5と上の表にはないが, F10=55も5の倍数である.
その辺を読んでみると
Fn+m=FmFn+1+ Fm-1Fn
という式があり, これが味噌である.
この証明は簡単だ.
Fn+3=Fn+2+Fn+1. Fn+2にFn+1+Fnを 代入すると Fn+3=2Fn+1+Fn.
この係数の 2はF3だし, 1はF2なので, この式は Fn+3=F3Fn+1+F2Fnになる.
同様にして
Fn+4=F4Fn+1+F3Fnになる.
この4をmにすると上の式になるわけだ.
証明はこんな具合である.
Fn+m+1={Fibonacci数の定義}Fn+m+Fn+m-1. このそれぞれに上の式を代入する.
FmFn+1+Fm-1Fn
Fm-1Fn+1+Fm-2Fn
Fm+Fm-1=Fm+1だし Fm-1+Fm-2=Fmなので, 上の式が得られた.
ところでFnkがFkの倍数である証明も 簡単であった.
Fk=FkだからFkの倍数.
Fk+k=FkFk+1+ Fk-1Fkだからそれぞれの項にFkがあり, Fkの倍数.
FnkがFkの倍数とすると
Fk+nk=FnkFk+1+ Fnk-1Fkとなり, 前の項にはFnk, 後の項にはFkがあり, それぞれFkの 倍数なので, F(n+1)kもFkの倍数である.
面白い.
0 件のコメント:
コメントを投稿