数论
881 字
约 3 分钟
Zeckendorf定理与黄金进制
Zeckendorf定理：任意一个正整数都可以唯一地表示成下述形式
证明 用数学归纳法证明．
当时，只能是，故命题成立；
设命题对所有小于的正整数均成立，考虑的情形．
注意到，对这个，存在唯一的正整数，使得，那么由归纳假设，有唯一表示，设
（时表示的唯一性可由，且中没有相邻的两个数均时，
可知）综上可知，命题成立．
定理中的表达式可以写成，其中，这与二进制表示有着相似之处，只是多了条件：中没有相邻的两个数均．
我们将这样的表达形式称作Zeckendorf表述法（又称斐波那契进制）．
由于斐波那契进制与一般进制相比，其并不是一个固定进制，所以在计算时会比较复杂．注意到，即相邻位值之比趋于黄金分割比．我们可以用进制（黄金进制）来代替斐波那契进制．
（2006年亚太地区数学奥林匹克 第2题）
证明：每一个正整数均可以表示成若干个的不同次幂之和．
证明 注意到，我们有
．对于任意正整数，先将其写成，每一次将其中个擦除，变为．
注意到这样的操作前后，的幂的个数是不变的，且每次所有指数之和减少．
经过次操作后，指数之和变为．
将到中的整数分为，，，这组．那么每次操作，我们将变为，或将变为，或将变为，即每次操作无法使上述的每一组中不含的某个次幂．
也就是说，经过次操作后，恰好每一组中均含的某个次幂，这与指数和为矛盾．
故经过不到次操作后，操作停止，此时已被表示成若干个的不同次幂之和．
如，，，，，……
这样的表示方法不唯一，上述证明给出了将表示为个的不同次幂之和的方法．事实上，类比Zeckendorf定理，在加上条件“不存在两个相邻的次幂”后，表示方法是唯一的．于是我们将此题进行了推广，此时的表示法被称作黄金进制，读者可以自行证明．
在黄金进制中，可以用有限小数或循环小数表示任意非负有理数，以及从有理数和生成的数域
中的非负元素．
用上述观点，我们可以解决以下问题：
（奥数教程高一分册）我们称一个由正整数组成的无穷数列为-数列，如果从第项起，该数列的每一项都等于它前面两项之和．问：能否将正整数集分划为
（1） 有限个互不相交的；
（2） 无穷多个互不相交的； -数列的并？（2020年巴西数学奥林匹克）对正整数，定义，，且对，．若对正整数，存在正整数以及正整数，使得，就称是“飞波的”．求证：存在无限多个正整数，不为“飞波的”．
在公众号查看原文 ↗
点公式可复制源码
留言
解法、疑问、勘误都可以说。公式用 LaTeX：行内
$…$，整行$$…$$。留言区还没开。想聊这道题，可以点上面的「在公众号查看原文」，到公众号那边留言。