二试-代数-数列 两种递推方式的数列

题 序列 定义为

证明：区间 中的整数不会出现在序列 中．

分析 这个数列的递推关系有两种选择，因此可能的序列有很多。我们先写出一些项，因为这是二阶递推数列，所以至少要保留相邻两项才能算出下一项。

从 开始，接下来 或 ， 给出 ， 给出 或 ，发现 重复。接下来 给出 或 , 给出 或 ， 给出 或 ， 和 重复。把重复出现的合并，把可以成为相邻项的连边，可以得到下面的图。

从图中左下角开始，向右或向上走出的路径都给出满足题目条件的序列。观察最下面一行可以写成 ，倒数第二行可以写成 ，因此猜测图中位于 位置的项是 。可以归纳证明这一点，从而得到题目的证明。

证明 我们归纳证明存在非负整数序列 ，使得 ，并且 ，，。当 时，，，命题成立。现在假设

并且 和 一个为1，另一个为0。

如果 ，取 ，命题成立。

如果 ，根据 ，，可知 ，， 是水平或者竖直的三个连续整点，命题依然成立。

因此数列中的每一项都是 的形式。若 ，，不妨设 。必然有 ，于是 ，矛盾。

因此数列的项不会出现在 中。

换种方式想一想，二阶递推数列把相邻的两项组合成向量，则下一个向量和这一个的关系是线性关系。两种不同的递推方式意味着乘以两个不同的矩阵。也就是说，如果 ，那么

如果这两个矩阵分别记为 ，则 是 任选 的序列左乘 次的结果。现在让这个题目变得可以不太复杂地解决的关键是 满足的乘法关系，具体是 ，。前者显然，后者可以验证如下

因此 的任何乘积序列可以把 的偶次幂提出变成 （是数量矩阵，和所有矩阵乘法交换）， 提出一个 去掉两个 ，最后得到 或者 的形式，再把 写回 ，于是得到 的形式。

也就是说， 总是可以从 开始，经过 步 的迭代，然后经过 步 的迭代得到。