齐肯多夫定理表示任何正整数都可以表示成若干个不连续的斐波那契数之和。这种和式称为齐肯多夫表述法。
对于任何正整数,其齐肯多夫表述法都可以用贪心算法选出每回最大可能的斐波那契数。
证明
以来表示斐波那契数。m为任意正整数。
- 若m是斐波那契数,命题成立
- 考虑最大的满足
- 考虑最大的满足
- 反证法:若:
- 和是连续斐波那契数。
- ,其中i是。
- 因为,存在i是不符合第2步的。
第3步说明了,其他的情况可以由数学归纳法看到亦符合命题。
参考
参见
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.