齐肯多夫定理

齐肯多夫定理表示任何正整数都可以表示成若干个不连续的斐波那契数之和。这种和式称为齐肯多夫表述法。

对于任何正整数，其齐肯多夫表述法都可以用贪心算法选出每回最大可能的斐波那契数。

证明

以$F_{n}$来表示斐波那契数。m为任意正整数。

1. 若m是斐波那契数，命题成立
2. 考虑最大的$n_{1}$满足$F_{n_{1}}<m<F_{n_{1}+1}$
3. $m'=m-F_{n_{1}}$
4. 考虑最大的$n_{2}$满足$F_{n_{2}}<m'<F_{n_{2}+1}$
5. $m''=m'-F_{n_{2}}$
6. 反证法：若$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<m'<m$，其他的情况可以由数学归纳法看到亦符合命题。

参考

• http://www.sftw.umac.mo/~fstitl/2000-topics/fibonacci.html （页面存档备份，存于互联网档案馆）

参见

• 爱德华·齐肯多夫