齊肯多夫定理

齊肯多夫定理表示任何正整數都可以表示成若干個不連續的斐波那契數之和。這種和式稱為齊肯多夫表述法。

對於任何正整數，其齊肯多夫表述法都可以用貪心算法選出每回最大可能的斐波那契數。

證明
以來表示斐波那契數。m為任意正整數。
若m是斐波那契數，命題成立
考慮最大的滿足

考慮最大的滿足

反證法：若：
和是連續斐波那契數。
，其中i是。
因為，存在i是不符合第2步的。

第3步說明了，其他的情況可以由數學歸納法看到亦符合命題。

參考
 http://www.sftw.umac.mo/~fstitl/2000-topics/fibonacci.html 
参见
 愛德華·齊肯多夫

Category:斐波那契数
Category:数论定理
Category:包含证明的条目