フィボナッチ数の話題

ご存じフィボナッチ数の話だ.

F₀=0, F₁=1, F_n+2=F_n+1+F_n
と定義され, 初めの方の値は

0	1	2	3	4	5	6	7	8	9
0	1	1	2	3	5	8	13	21	34

ところでTAOCPの第1巻に,
F_3nは2(=F₃)の倍数
F_4nは3(=F₄)の倍数
F_5nは5(=F₅)の倍数
F_knはF_kの倍数
と書いてあった.

たしかにF₃, F₆, F₉は偶数だし,
F₅と上の表にはないが, F₁₀=55も5の倍数である.

その辺を読んでみると

F_n+m=F_mF_n+1+ F_m-1F_n

という式があり, これが味噌である.

この証明は簡単だ.

F_n+3=F_n+2+F_n+1. F_n+2にF_n+1+F_nを 代入すると F_n+3=2F_n+1+F_n.
この係数の 2はF₃だし, 1はF₂なので, この式は F_n+3=F₃F_n+1+F₂F_nになる.

同様にして

F_n+4=F₄F_n+1+F₃F_nになる.

この4をmにすると上の式になるわけだ.

証明はこんな具合である.

F_n+m+1={Fibonacci数の定義}F_n+m+F_n+m-1. このそれぞれに上の式を代入する.

F_mF_n+1+F_m-1F_n
F_m-1F_n+1+F_m-2F_n
F_m+F_m-1=F_m+1だし F_m-1+F_m-2=F_mなので, 上の式が得られた.

ところでF_nkがF_kの倍数である証明も 簡単であった.

F_k=F_kだからF_kの倍数.
F_k+k=F_kF_k+1+ F_k-1F_kだからそれぞれの項にF_kがあり, F_kの倍数.

F_nkがF_kの倍数とすると
F_k+nk=F_nkF_k+1+ F_nk-1F_kとなり, 前の項にはF_nk, 後の項にはF_kがあり, それぞれF_kの 倍数なので, F_(n+1)kもF_kの倍数である.

面白い.