Putnam 2006, Problem A-3

Let $1, 2, 3, \ldots, 2005, 2006, 2007, 2009, 2012, 2016, \ldots$ be a sequence defined by $x_k = k$ for $k = 1, 2, \ldots, 2006$ and $x_{k+1} = x_k + x_{k-2005}$ for $k \geq 2006$. Show that the sequence has 2005 consecutive terms each divisible by 2006.

Solution:
We first observe that given any sequence of integers $x_1, x_2, \ldots$ satisfying a recursion
$$x_k = f(x_{k-1}, \ldots, x_{k-n}) \quad (k > n),$$
where $n$ is fixed and $f$ is a fixed polynomial of $n$ variables with integer coefficients, for any positive integer $N$, the sequence modulo $N$ is eventually periodic. This is simply because there are only finitely many possible sequences of $n$ consecutive values modulo $N$, and once such a sequence is repeated, every subsequent value is repeated as well.

We next observe that if one can rewrite the same recursion as
$$x_{k-n} = g(x_{k-n+1}, \ldots, x_k) \quad (k > n),$$
where $g$ is also a polynomial with integer coefficients, then the sequence extends uniquely to a doubly infinite sequence $\ldots, x_{-1}, x_0, x_1, \ldots$ which is fully periodic modulo any $N$. That is the case in the situation at hand, because we can rewrite the given recursion as
$$x_{k-2005} = x_{k+1} - x_k.$$
It thus suffices to find 2005 consecutive terms divisible by $N$ in the doubly infinite sequence, for any fixed $N$ (so in particular for $N = 2006$). Running the recursion backwards, we easily find
$$x_1 = x_0 = \cdots = x_{-2004} = 1$$
$$x_{-2005} = \cdots = x_{-4009} = 0,$$
yielding the desired result.