跳转到内容

齊肯多夫定理

本页使用了标题或全文手工转换
维基百科,自由的百科全书

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

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

證明

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

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

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

參考

参见