齊肯多夫定理

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

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

證明

以${\displaystyle F_{n}}$ 來表示斐波那契數。m為任意正整數。

1. 若m是斐波那契數，命題成立
2. 考慮最大的${\displaystyle n_{1}}$ 滿足${\displaystyle F_{n_{1}}<m<F_{n_{1}+1}}$ 
3. ${\displaystyle m'=m-F_{n_{1}}}$ 
4. 考慮最大的${\displaystyle n_{2}}$ 滿足${\displaystyle F_{n_{2}}<m'<F_{n_{2}+1}}$ 
5. ${\displaystyle m''=m'-F_{n_{2}}}$ 
6. 反證法：若${\displaystyle n_{1}=n_{2}+1}$ ：
   • ${\displaystyle F_{n_{2}}}$ 和${\displaystyle F_{n_{1}}}$ 是連續斐波那契數。
   • ${\displaystyle F_{n_{2}}+F_{n_{1}}=F_{i}}$ ，其中i是${\displaystyle n_{1}+1}$ 。
   • 因為${\displaystyle i>n_{1}}$ ，存在i是不符合第2步的。

第3步說明了${\displaystyle 0<m'<m}$ ，其他的情況可以由數學歸納法看到亦符合命題。

參考

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

参见

• 愛德華·齊肯多夫