齐肯多夫定理查看源代码讨论查看历史

齐肯多夫(Zeckendorf)定理表示任何正整数都可以表示成若干个不连续的斐波那契数（不包括第一个斐波那契数）之和。这种和式称为齐肯多夫表述法。^[1]

定理定义

对于任何正整数，其齐肯多夫表述法都可以由贪心算法（即每次选出最大可能的斐波那契数）得到。

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