§C3.2ゼッケンドルフの定理

証明.$F_1\ge1$、$F_2\ge2$であり、$F_k\ge k$かつ$F_{k+1}\ge k+1$ならば$F_{k+2}=F_{k+1}+F_k\ge2k+1\ge k+2$である。したがって、フィボナッチ数列は上に有界でない。

$N$を正の整数とし、$N$より小さいすべての正の整数が条件を満たす表示を持つと仮定する。$F_1=1\le N$であり、フィボナッチ数列は上に有界でないので、$F_k\le N$を満たす最大の番号$k_1$が存在する。$k_1$の最大性から$N<F_{k_1+1}$である。

$k_1=1$ならば$N<F_2=2$より$N=1=F_1$である。

$k_1\ge2$ならば$F_{k_1+1}=F_{k_1}+F_{k_1-1}$であるから、$N < F_{k_1} + F_{k_1-1}$すなわち

を得る。$N-F_{k_1}=0$ならば$N=F_{k_1}$である。$N-F_{k_1}>0$ならば$N-F_{k_1}<N$であるから、帰納法の仮定により$N-F_{k_1}$は条件を満たす表示を持つ。その表示に現れる最大の番号を$j$とすると、$F_j \le N - F_{k_1} < F_{k_1-1}$であり、フィボナッチ数が狭義に単調増加することから$j<k_1-1$、すなわち$j\le k_1-2$である。したがって、この表示に$F_{k_1}$を加えると、番号の差が$2$以上である$N$の表示を得る。▨

証明.$k=1$ならば$r=1$であり、和は$F_1=1<2=F_2$である。$k=2$でも$r=1$であり、和は$F_2=2<3=F_3$である。

$k\ge3$とし、$k$より小さいすべての番号について主張が成り立つと仮定する。$r=1$ならば、和は$F_k<F_{k+1}$である。$r\ge2$ならば$k_2\le k-2$であり、$F_{k_2} + \cdots + F_{k_r}$は最大の番号が$k_2$である和なので、帰納法の仮定により$F_{k_2+1}$より小さい。フィボナッチ数が狭義に単調増加することと$k_2+1\le k-1$から、

を得る。▨

証明.$N$を正の整数とし、$N$より小さいすべての正の整数について一意性が成り立つと仮定する。$N$の条件を満たす二つの表示

を取り、番号はいずれも大きい順に並べる。

定理 4.1を第一の表示に適用すると$N<F_{k_1+1}$であり、$F_{k_1}$は和の一部であるから$F_{k_1}\le N$である。すなわち

が成り立つ。同じ議論により$F_{l_1}\le N<F_{l_1+1}$も成り立つ。フィボナッチ数は狭義に単調増加するので、$F_k\le N<F_{k+1}$を満たす番号$k$はただ一つである。したがって$k_1=l_1$である。

両方の表示から共通の項$F_{k_1}$を除くと、残る和はどちらも$N-F_{k_1}$に等しい。$r=1$ならば$N-F_{k_1}=0$であり、第二の表示に残る正の項も無いので$s=1$である。$s=1$の場合も同様に$r=1$である。$r,s\ge2$ならば$0<N-F_{k_1}<N$であり、除いた後の二つの番号列はいずれも条件を満たす。帰納法の仮定により二つの残りの表示は一致するので、もとの二つの表示も一致する。▨