フィボナッチ数の話題

前回, この話題では F_n+1F_n-1-F_n² =(-1)ⁿ を証明したが, 実はもっと簡単の単であった.

n=1の時は

1·0 -1·1=-1
つまり(-1)¹ だ.

n+1の時の式は

F_n+2F_n - F_n+1²

このF_n+2とF_n+1の一つを定義により前の2項の和に書き換える.

(F_n+1+F_n)F_n - F_n+1(F_n+F_n-1) = F_n² - F_n+1F_n-1 = -(-1)ⁿ = (-1)ⁿ⁺¹

フィボナッチ数の話題

TAOCPのフィボナッチ数の話題(1.2.8)には F_n+1F_n-1-F_n² =(-1)ⁿ というこれも気になる式がある.

1·0-1·1=-1
2·1-1·1=1
3·1-2·2=-1
5·2-3·3=1
8·3-5·5=-1
たしかに.

証明したくなった. 式が沢山でてくるので, Texで書いたものが下である.



式0が証明したいもの. F_nはφとそのハットを使って式1の ように書ける.

式2がそれらの定義だ.

φとφハットの積や比は, 式3と4のようだ.

さて, 式0の左辺に式1を代入したのが, 式5である.

とりあえず 1/√を忘れて, 式6のように第1項を掛ける. 第2項の積は 式7のようになる.

6から7を引くと, 式8が得られるが, 先程保留していた分母の√5が2個ずつ あったので, それで5が消え, (-1)ⁿとなる.

フィボナッチ数の話題

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

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の倍数である.

面白い.