查看“︁齊肯多夫定理”︁的源代码

{{NoteTA
|G1 = math
|G2 = IT
|1=zh-tw:費波那契;zh-hk:費波那契;zh-cn:斐波那契;
}}
'''齊肯多夫定理'''表示任何正[[整數]]都可以表示成若干個不連續的[[斐波那契數]]之和。這種和式稱為'''齊肯多夫表述法'''。

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

==證明==
以<math>F_n</math>來表示斐波那契數。m為任意正整數。
#若m是斐波那契數，命題成立
#考慮最大的<math>n_1</math>滿足<math>F_{n_1} < m < F_{n_1+1}</math>
#<math>m'=m-F_{n_1}</math>
#考慮最大的<math>n_2</math>滿足<math>F_{n_2} < m' < F_{n_2+1}</math>
#<math>m''=m'-F_{n_2}</math>
#[[反證法]]：若<math>n_1=n_2 + 1</math>：
#*<math>F_{n_2}</math>和<math>F_{n_1}</math>是連續斐波那契數。
#*<math>F_{n_2} + F_{n_1}=F_{i}</math>，其中i是<math>n_1+1</math>。
#*因為<math>i>n_1</math>，存在i是不符合第2步的。

第3步說明了<math>0 < m' < m</math>，其他的情況可以由[[數學歸納法]]看到亦符合命題。

==參考==
* http://www.sftw.umac.mo/~fstitl/2000-topics/fibonacci.html {{Wayback|url=http://www.sftw.umac.mo/~fstitl/2000-topics/fibonacci.html |date=20081030081449 }}
==参见==
* [[愛德華·齊肯多夫]]

[[Category:斐波那契数]]
[[Category:数论定理]]
[[Category:包含证明的条目]]