跳至內容

齊肯多夫定理

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

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

證明

來表示費波那契數。m為任意正整數。

  1. 若m是費波那契數,命題成立
  2. 考慮最大的滿足
  3. 考慮最大的滿足
  4. 反證法:若
    • 是連續費波那契數。
    • ,其中i是
    • 因為,存在i是不符合第2步的。

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

參考

參見