今日上某数学课的时候有一道这样的题目：
给定数列 $a_n = a_{n - 3} + a_{n - 2}; a_0 = 3, a_1 = 0, a_2 = 2$ ，证明如果 $p$ 为质数，有 $p|a_p$ 。
这个数列是 oeis 上的 A001608。
这个问题已经有了很多种证明方法，例如B. H. Neumann and L. G. Wilson, Some Sequences like Fibonacci’s, Fibonacci Quart., 17(1), 1979, p. 83.和E. B. Escott, Problem 151, Amer. Math. Monthly, 15 (1908), 209.。这两份 pdf 的本博客链接：neumann.pdf, 151.pdf。
本处介绍一种思路较为简单的证明方法。
考虑 $a_n$ 的意义，将 $a_n$ （$n\ge 3$）作如下定义：一个长 $n$ 的环按顺序标号 $1$ 到 $n$，环上标号为 $u$ 的点有权值 $w_u$，权值为 $0$ 或 $1$ ，且每个权值为 $1$ 的点到其他权值为 $1$ 的点的最短距离为 $2$ 或 $3$ 。求方案数。
显然对于 $a_3 = 3$ 定义成立。现在我们证明对 $n > 3$ 该定义成立。
我们假设标号最小的为 $1$ 的点的标号为 $x$ ，则必然有 $w_{x + 2} = 1$ 或 $w_{x + 3} = 1$ 。
- 若 $w_{x + 2} = 1$ ，该方案等价于删去编号为 $x + 1, x + 2$ 的点（显然删去后仍然合法），有方案数 $a_{n - 2}$ 。
- 若 $w_{x + 3} = 1$ ，该方案等价于删去编号为 $x + 1, x + 2, x + 3$ 的点，有方案数 $a_{n - 3}$ 。
综上，有 $a_n = a_{n - 2} + a_{n - 3}$ 。
对于一个质数 $p\ge 3$ ，因为 $p$ 不含有 $1, p$ 以外的因子，所以对于任意一种合法的方案，显然将这种方案任意旋转仍然合法。所以有 $p|a_p$ 。
显然上述证明可以推广到J. Shallit, J. P. Yamron, On linear recurrences and divisibility by primes, Fib. Quart. 22 (4) (1984) 366.（shallit2.pdf）所提到的一类数列:
给定数列 $a_n = a_{n - k + 1} + a_{n - k}; a_0 = k, a_1 = a_2 = \cdots = a_{k - 2} = 0, a_{k - 1} = k - 1$ ，对于质数 $p\ge k$ ，$p|a_p$ 。
然而这种做法无法证明类似如下的题目：
给定数列 $a_n = a_{n - 1} + a_{n - 2} + (-1)^n; a_0 = 3, a_1 = 0, a_2 = 4$ ，证明如果 $p$ 为质数，有 $p|a_p$ 。
而 neumann.pdf 中有对于任意此类型数列的证明，而本人并未看懂，故弃坑。