1996 USAMO 第 4 题

An $n$-term sequence $(x_1, x_2, \ldots, x_n)$ in which each term is either 0 or 1 is called a binary sequence of length $n$. Let $a_n$ be the number of binary sequences of length n containing no three consecutive terms equal to 0, 1, 0 in that order. Let $b_n$ be the number of binary sequences of length $n$ that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that $b_{n+1} = 2a_n$ for all positive integers $n$.

(proposed by Kiran Kedlaya)

$n$ 项的序列 $(x_1, x_2, \ldots, x_n)$，其中每项不是 0 就是 1，称为长度为 $n$ 的二进制序列。设 $a_n$ 为长度为 n 的二进制序列的数量，其中不包含按顺序等于 0、1、0 的三个连续项。令 $b_n$ 为长度为 $n$ 的二进制序列的数量，其中不包含按顺序等于 0、0、1、1 或 1、1、0、0 的四个连续项。证明对于所有正整数 $n$，$b_{n+1} = 2a_n$。

(由基兰·凯德拉亚提议)