齊肯多夫定理表示任何正整數都可以表示成若干個不連續的斐波那契數之和。這種和式稱為齊肯多夫表述法。
對於任何正整數，其齊肯多夫表述法都可以用貪心算法選出每回最大可能的斐波那契數。
證明
以F_n來表示斐波那契數。m為任意正整數。
#若m是斐波那契數，命題成立
#考慮最大的n_1滿足F_{n_1}
#m'=m-F_{n_1}
#考慮最大的n_2滿足F_{n_2}
#m*=m'-F_{n_2}
#反證法：若n_1=n_2 + 1：
#*F_{n_2}和F_{n_1}是連續斐波那契數。
#*F_{n_2} + F_{n_1}=F_{i}，其中i是n_1+1。
#*因為i>n_1，存在i是不符合第2步的。
第3步說明了0 ，其他的情況可以由數學歸納法看到亦符合命題。
參考
参见
- 愛德華·齊肯多夫
评论 (0)