齊肯多夫定理

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

基本介紹

• 中文名：齊肯多夫定理
• 別稱：齊肯多夫表述法
• 提出者：齊肯多夫
• 套用學科：數學

定理定義

對於任何正整數，其齊肯多夫表述法都可以由貪心算法（即每次選出最大可能的斐波那契數）得到。

驗證推導

以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都成立。