跳转到内容

齐肯多夫定理

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

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

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

证明

来表示斐波那契数。m为任意正整数。

  1. 若m是斐波那契数,命题成立
  2. 考虑最大的满足
  3. 考虑最大的满足
  4. 反证法:若
    • 是连续斐波那契数。
    • ,其中i是
    • 因为,存在i是不符合第2步的。

第3步说明了,其他的情况可以由数学归纳法看到亦符合命题。

参考

参见