Европейская математическая олимпиада среди девочек (EGMO). 2020 год. Нидерланды

Целые положительные числа $a_{0}, a_{1}, a_{2}, \ldots, a_{3030}$ таковы, что $2 a_{n+2}=a_{n+1}+4 a_{n}$ при всех $n=0,1,2, \ldots, 3028.$ Докажите, что хотя бы одно из чисел $a_{0}, a_{1}, a_{2}, \ldots, a_{3030}$ делится на $2^{2020}$.

Комментарий/решение

Докажем по индукции, что в любой последовательности длины $3k+1$, удовлетворяющей данному рекуррентному соотношению, хотя бы один член делится на $4^k$.

$\textbf{База индукции:}$ $k = 0$. Последовательность длины 1, утверждение очевидна.

$\textbf{Индукционный переход:}$ Предположим, утверждение верно для некоторого $k \geq 0$. Рассмотрим последовательность $a_0, a_1, \ldots, a_{3k}$ длины $3k+1$, удовлетворяющую соотношению.

Из рекуррентного условия следует:

$$ 2a_{n+2} = a_{n+1} + 4a_n \quad \Rightarrow \quad a_{n+1} \equiv 2a_{n+2} \pmod{4}. $$

Отсюда получаем:

- $a_{n+1}$ делится на 2 для всех $n$, значит, все члены $a_1, a_2, \ldots, a_{3k-1}$ делятся на 2.

- Из сравнения по модулю 4 следует, что все $a_1, a_2, \ldots, a_{3k-2}$ делятся на 4.

Рассмотрим теперь последовательность

$$ b_n = \frac{a_{n+1}}{4}, \quad n = 0, 1, \ldots, 3(k-1). $$

Она имеет длину $3(k-1)+1$ и удовлетворяет тому же рекуррентному соотношению:

$$ 2b_{n+2} = 2 \cdot \frac{a_{n+3}}{4} = \frac{a_{n+3}}{2}, \quad b_{n+1} + 4b_n = \frac{a_{n+2}}{4} + 4 \cdot \frac{a_{n+1}}{4} = \frac{a_{n+2} + 4a_{n+1}}{4}. $$

Из исходного соотношения $2a_{n+3} = a_{n+2} + 4a_{n+1}$ получаем $\dfrac{a_{n+3}}{2} = \dfrac{a_{n+2} + 4a_{n+1}}{4}$, что доказывает выполнение рекуррентности для $b_n$.

По предположению индукции для последовательности $b_0, \ldots, b_{3(k-1)}$ существует индекс $m$ такой, что $b_m$ делится на $4^{k-1}$. Тогда соответствующий член исходной последовательности $a_{m+1} = 4b_m$ делится на $4 \cdot 4^{k-1} = 4^k .\square$