基本介紹
- 中文名：齊肯多夫定理
- 外文名：Zeckendorf theorem
- 別名：齊肯多夫表述法
- 提出者：齊肯多夫
- 套用學科：數學
定理定義,驗證推導,
定理定義
對於任何正整數，其齊肯多夫表述法都可以由貪心算法（即每次選出最大可能的斐波那契數）得到。
驗證推導
以F(n)來表示第n個斐波那契數。m為任意正整數。
當m=1,2,3時，因為1=F(2),2=F(3),3=F(4),所以命題成立。下面採用數學歸納法證明定理對任何m均成立。
假設定理對任何小於m的正整數數都成立。下證命題對m也成立。
（1）若m是斐波那契數，則命題對m也成立。
（2）若m不是斐波那契數，設n1是滿足F(n1)＜ m ＜ F(n1 +1)的最大正整數。
設m'=m-F(n1),則m'=m-F(n1)＜F(n1+1)-F(n1)=F(n1-1)，即m'＜F(n1-1)。
m'＜m，所以由歸納假設，m'可以表示成不連續的斐波那契數之和，即m'=F(n2)+F(n3)+...+F(nt),其中n2＞n3＞...＞nt,且是不連續的整數。又m'＜F(n1-1)，所以n2＜n1-1，即n2與n1也是不連續的整數。
故m=F(n1)+m'=F(n1)+F(n2)+F(n3)+...+F(nt),且n1＞n2＞...＞nt是不連續的整數。
因此，命題對m也成立。
綜合（1）（2），由數學歸納法，齊肯多夫定理對任何正整數m都成立。
