竞赛数学：递推序列整除性证明——存在项被2018²⁰¹⁸整除

Let's break down how to prove this result step by step. The key here is using properties of linear recurrence sequences, modular arithmetic, and mathematical induction—we'll go with induction since it's more straightforward once we have the right setup.

First, define $M = 2018^{2018}$—our goal is to show there exists some integer $k$ where $x_k \equiv 0 \pmod{M}$.

The given recurrence is:
$$x_{n+1} = 2018x_n + 2019x_{n-1} \quad \text{for } n \geq 2$$
with initial terms $x_1 = 2018$, $x_2 = 1$.

A critical observation is solving the characteristic equation for this linear recurrence:
$$r^2 - 2018r - 2019 = 0$$
Factoring gives roots $r = 2019$ and $r = -1$, so we can write the closed-form formula for the sequence:
$$x_n = A \cdot 2019^n + B \cdot (-1)^n$$
Solving for constants $A$ and $B$ using the initial terms gives:
$$A = \frac{1}{2020}, \quad B = \frac{2020 - 2019^2}{2020}$$
So:
$$x_n = \frac{2019^n + (-1)^n(2020 - 2019^2)}{2020}$$
Since all $x_n$ are integers, the numerator is always divisible by 2020.

We'll prove by induction that for every integer $k \geq 1$, there exists some index $n_k$ such that $x_{n_k} \equiv 0 \pmod{2018^k}$. Our target is $k = 2018$.

Base Case ($k=1$) #

$x_1 = 2018$, which is clearly divisible by $2018^1 = 2018$. The base case holds.

Inductive Step #

Assume that for some $m \geq 1$, there exists $n_m$ where $x_{n_m} \equiv 0 \pmod{2018^m}$. We need to show there exists $n_{m+1}$ such that $x_{n_{m+1}} \equiv 0 \pmod{2018^{m+1}}$.

First, note that $x_{n_m - 1}$ cannot be divisible by 2018: if it were, substituting into the recurrence would imply $x_{n_m} = 2018x_{n_m-1} + 2019x_{n_m-2} \equiv 2019x_{n_m-2} \pmod{2018}$. Since $x_{n_m} \equiv 0 \pmod{2018}$, this would mean $x_{n_m-2} \equiv 0 \pmod{2018}$. Repeating this backward leads to $x_2 = 1 \equiv 0 \pmod{2018}$, a contradiction. Thus, $\gcd(x_{n_m-1}, 2018) = 1$.

Using the closed-form formula, rewrite $x_{n_m + t}$:
$$x_{n_m + t} = 2019^t \cdot A \cdot 2019^{n_m} + (-1)^t \cdot B \cdot (-1)^{n_m}$$
Since $x_{n_m} = A \cdot 2019^{n_m} + B \cdot (-1)^{n_m} = 2018^m \cdot t_0$ (for some integer $t_0$), substitute $A \cdot 2019^{n_m} = 2018^m t_0 - B \cdot (-1)^{n_m}$ into the above:
$$x_{n_m + t} = 2018^m t_0 \cdot 2019^t + B \cdot (-1)^{n_m} \left( (-1)^t - 2019^t \right)$$

We want this to be divisible by $2018^{m+1}$. Choose even $t = 2s$, so the condition becomes $(2019²⁾s \equiv 1 \pmod{2018^{m+1}}$.

Note that $2019^2 = (2018 + 1)^2 = 1 + 2018 \cdot 2020$. Using the binomial theorem:
$$(2019²⁾s = 1 + s \cdot 2018 \cdot 2020 + \binom{s}{2}(2018 \cdot 2020)^2 + \dots$$
Modulo $2018^{m+1}$, all terms beyond the first two vanish, so we need:
$$1 + s \cdot 2018 \cdot 2020 \equiv 1 \pmod{2018^{m+1}}$$
Simplifies to $s \cdot 2020 \equiv 0 \pmod{2018^m}$. Since $\gcd(2020, 2018^m) = 2$, we can choose $s = 2^{m-1} \cdot 1009^m \cdot k$ (for any integer $k$), which makes $s \cdot 2020$ divisible by $2018^m$.

For this $t = 2s$, $(-1)^t - 2019^t \equiv 0 \pmod{2018^{m+1}}$, and $2018^m t_0 \cdot 2019^t$ is divisible by $2018^{2m} \geq 2018^{m+1}$ (since $m \geq 1$). Thus:
$$x_{n_m + t} \equiv 0 \pmod{2018^{m+1}}$$
This completes the inductive step.

By induction, for every $k \geq 1$, there exists a term in the sequence divisible by $2018^k$. Setting $k = 2018$, we conclude that there must be some term in the sequence divisible by $2018^{2018}$.

内容的提问来源于stack exchange，提问作者Mojimoji