周期数列

观察

一项一项往下走，盯住钟面旁边的小方格。相邻两项 $(a_{n}, a_{n + 1})$ 一共只有 $7 \times 7 = 49$ 种可能。数列能不能永远不重复？
走到第一次重复的那一对时，按道理后面会发生什么？再多走几项（或者按“走到第一次重复”）验证一下。
把 $m$ 改成 $8$ 、 $q$ 改成 $2$ 。这一次重复出现的那一对，是开头那一对吗？（看“前段长度 $μ$ ”。）
再把 $q$ 改成 $3$ 。前段消失了。 $q$ 和 $m$ 是否互素，起了什么作用？

如果存在正整数 $T$ 和 $n_{0}$ ，使得对一切 $n \geq n_{0}$ 都有 $a_{n + T} = a_{n}$ ，就称 ${a_{n}}$ 是周期数列， $T$ 是它的一个周期；若 $n_{0} = 1$ （从头就开始循环），叫纯周期数列。最小的那个 $T$ 叫最小正周期。整数数列本身未必有周期，但取模 $m$ 的余数后，往往就有了——这叫模 $m$ 周期数列。

先猜后证

数列 $a_{1} = 1, a_{2} = 2, a_{n + 2} = a_{n + 1} - a_{n}$ 。 $a_{2026}$ 是多少？

先选定答案，才能看到结论。

为什么

定理：整数线性递推数列模 m 一定是周期数列

第 1 / 4 步

状态
$a_{n + 2} \equiv 3 a_{n + 1} + a_{n} (mod 7)$ 。下一项只看前两项，所以“相邻两项”这一对就是数列的状态：知道了它，后面的一切都确定了。

$(a_{n}, a_{n + 1}) 决定 a_{n + 2}, a_{n + 3}, \dots$
抽屉
重复了
为什么从头就循环

同样的论证对任何“下一项由前 $k$ 项决定、每一项只有有限种取值”的数列都有效：状态有限，迟早重复，重复之后就循环。

如果去掉一个条件

Break it

反例实验室：去掉一个条件

结论：数列模 $m$ 是纯周期的（从第一项就开始循环）

$a_{n + 2} \equiv a_{n + 1} + 3 a_{n} (mod 8)$ ， $a_{0} = a_{1} = 1$ 。 $(3, 8) = 1$ 。按“走到第一次重复”：重复的正是开头那一对 $(1, 1)$ 。

练一练

练习 1基础

$a_{1} = 3, a_{2} = 5, a_{n + 2} = a_{n + 1} - a_{n}$ 。求前 $100$ 项的和。

练习 2基础

$3^{2026}$ 的个位数字是几？

练习 3提高

$a_{0} = 0, a_{1} = 1, a_{n + 2} = 2 a_{n + 1} + a_{n}$ 。数列模 $7$ 的最小正周期是多少？

练习 4挑战

$a_{1} = 2, a_{n + 1} = \frac{1 + a _{n}}{1 - a _{n}}$ 。求 $a_{2026}$ 。

观察

为什么

定理：整数线性递推数列模 m 一定是周期数列

如果去掉一个条件

反例实验室：去掉一个条件

练一练

错误博物馆 · 本站展品

两个周期合起来，只想到最小公倍数