齊肯多夫定理

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

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

證明

以${\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 （頁面存檔備份，存於網際網路檔案館）

參見

• 愛德華·齊肯多夫