数论
Zeckendorf定理与黄金进制
正文文字 881 字公式 90 处
Zeckendorf定理：任意一个正整数𝑛都可以唯一地表示成下述形式
公式：n=a_kF_k+a_{k-1}F_{k-1}+\cdots+a_1F_1\text{．}证明 用数学归纳法证明．
当𝑛=1时，只能是𝑛=𝐹_(1)，故命题成立；
设命题对所有小于𝑛的正整数均成立，考虑𝑛的情形．
注意到，对这个𝑛，存在唯一的正整数𝑘，使得𝐹_(𝑘)≤𝑛<𝐹_(𝑘+1)，那么由归纳假设，𝑛−𝐹_(𝑘)有唯一表示，设
公式：n-F_k=a_sF_s+a_{s-1}F_{s-1}+\cdots+a_1F_1\text{．}
公式：n=F_k+a_sF_s+a_{s-1}F_{s-1}+\cdots+a_1F_1\text{．}（𝑛=𝐹_(𝑘)时表示的唯一性可由𝑠<𝑘，且𝑎_(1),𝑎_(2),⋯,𝑎_(𝑘)中没有相邻的两个数均1时，
公式：a_sF_s+a_{s-1}F_{s-1}+\cdots+a_1F_1< F_{s+1}可知）综上可知，命题成立．
定理中的表达式可以写成𝑛=(𝑎_(𝑘)𝑎_(𝑘−1)⋯𝑎_(1))_(𝐹)，其中𝑎_(𝑖)∈{0,1}，这与二进制表示有着相似之处，只是多了条件：𝑎_(1),𝑎_(2),⋯,𝑎_(𝑘)中没有相邻的两个数均1．
我们将这样的表达形式称作Zeckendorf表述法（又称斐波那契进制）．
由于斐波那契进制与一般进制相比，其并不是一个固定进制，所以在计算时会比较复杂．注意到lim_(𝑛→∞)(𝐹_(𝑛+1))/(𝐹_(𝑛))=(√(5)+1)/(2)，即相邻位值之比趋于黄金分割比．我们可以用(√(5)+1)/(2)进制（黄金进制）来代替斐波那契进制．
（2006年亚太地区数学奥林匹克 第2题）
证明：每一个正整数均可以表示成若干个𝜑=(√(5)+1)/(2)的不同次幂之和．
证明 注意到𝜑^(𝑛)=𝜑^(𝑛−1)+𝜑^(𝑛−2)，我们有
公式：2\varphi^n=\varphi^n+\varphi^{n-1}+\varphi^{n-2}=\varphi^{n+1}+\varphi^{n-2}．对于任意正整数𝑘，先将其写成𝑘=𝑘⋅𝜑^(0)，每一次将其中2个𝜑^(𝑛)擦除，变为𝜑^(𝑛+1)+𝜑^(𝑛−2)．
注意到这样的操作前后，𝜑的幂的个数是不变的，且每次所有指数之和减少1．
经过3𝑘^(2)次操作后，指数之和变为−3𝑘^(2)．
将−3𝑘到−1中的整数分为(−1,−2,−3)，(−4,−5,−6)，⋯，(−3𝑘+2,−3𝑘+1,−3𝑘)这𝑘组．那么每次操作，我们将𝜑^(𝑛)变为𝜑^(𝑛−2)，或将𝜑^(𝑛−2)变为𝜑^(𝑛−1)，或将𝜑^(𝑛−1)变为𝜑^(𝑛)，即每次操作无法使上述的每一组中不含𝜑的某个次幂．
也就是说，经过3𝑘^(2)次操作后，恰好每一组中均含𝜑的某个次幂，这与指数和为−3𝑘^(2)矛盾．
故经过不到3𝑘^(2)次操作后，操作停止，此时𝑘已被表示成若干个𝜑=(√(5)+1)/(2)的不同次幂之和．
如1=𝜑^(0)，2=𝜑^(1)+𝜑^(−2)，3=𝜑^(1)+𝜑^(0)+𝜑^(−2)，4=𝜑^(2)+𝜑^(0)+𝜑^(−3)+𝜑^(−4)，5=𝜑^(2)+𝜑^(1)+𝜑^(−2)+𝜑^(−3)+𝜑^(−4)，……
这样的表示方法不唯一，上述证明给出了将𝑘表示为𝑘个𝜑=(√(5)+1)/(2)的不同次幂之和的方法．事实上，类比Zeckendorf定理，在加上条件“不存在两个相邻的次幂”后，表示方法是唯一的．于是我们将此题进行了推广，此时的表示法被称作黄金进制，读者可以自行证明．
在黄金进制中，可以用有限小数或循环小数表示任意非负有理数，以及从有理数和√(5)生成的数域
中的非负元素．
用上述观点，我们可以解决以下问题：
（奥数教程高一分册）我们称一个由正整数组成的无穷数列为𝐹-数列，如果从第3项起，该数列的每一项都等于它前面两项之和．问：能否将正整数集分划为
（1） 有限个互不相交的；
（2） 无穷多个互不相交的； 𝐹-数列的并？（2020年巴西数学奥林匹克）对正整数𝑎，定义𝐹(𝑎)1=1，𝐹(𝑎)2=𝑎，且对𝑛>2，𝐹(𝑎)𝑛=𝐹(𝑎)𝑛−1+𝐹(𝑎)𝑛−2．若对正整数𝑥，存在正整数𝑎以及正整数𝑛>3，使得𝑥=𝐹(𝑎)𝑛，就称𝑥是“飞波的”．求证：存在无限多个正整数，不为“飞波的”．
留言
正常留言提交后可直接显示，无需人工审核；仍会经过防刷与垃圾内容过滤。请不要留下手机号等私人信息。解法、疑问都可以说；公式用 LaTeX：行内
$…$，整行$$…$$。