Bài toán 23.[EGMO, 2020] Cho dãy các số nguyên dương $a_0, a_1, \ldots, a_{3030}$ thỏa mãn $$2a_{n+2}=a_{n+1}+4a_{n}$$ với mọi $n=0, 1, 2, \ldots, 3028$. Chứng minh rằng trong các số $a_0, a_1, \ldots, a_{3030}$ có ít nhất một số chia hết cho $2^{2020}$.

Bài toán 23.[EGMO, 2020] Cho dãy các số nguyên dương $a_0, a_1, \ldots, a_{3030}$ thỏa mãn $$2a_{n+2}=a_{n+1}+4a_{n}$$ với mọi $n=0, 1, 2, \ldots, 3028$. Chứng minh rằng trong các số $a_0, a_1, \ldots, a_{3030}$ có ít nhất một số chia hết cho $2^{2020}$.

Lời giải

Ta sẽ chứng minh kết quả tổng quát hơn: \textit{Với mọi số nguyên dương $k\le 1010$, trong đó các số $a_0, a_1, \ldots, a_{1010}$ có ít nhất một số chia hết cho $2^{2k}$}.
Ta chứng minh bằng quy nạp theo $k$:

• Với $k=1$, ta có $a_2=2a_3-4a_1$ chia hết cho $2$, do đó $a_1=2a_2-4a_0$ chia hết cho $4$. Suy ra khẳng định đúng với $k=1$.
• Giả sử khẳng định đúng đến $k\ (1\le k\le 1009)$. Ta có $a_{n+1}=2a_{n+2}-4a_n$ chia hết cho $2$ với mọi $0\le n\le 3028$, do đó $a_n$ chia hết cho $2$ với mọi $1\le n\le 3029$. Suy ra $a_{n+1}=2a_{n+2}-4a_n$ chia hết cho $4$ với mọi $0\le n\le 3027$, do đó $a_n$ chia hết cho $4$ với mọi $1\le n\le 3028$.
  Bây giờ, xét dãy $b_0, b_1, \ldots, b_{3027}$ với $b_i=\dfrac{a_{i+1}}{4}$ với mọi $0\le i\le 3027$. Khi đó ta có $$2b_{n+2}=b_{n+1}+4b_{n}, 0\le n\le 3025.$$ Chú ý rằng $1\le k\le 1009$ nên $3k\le 3027$. Do đó, các số $b_0, b_1, \ldots, b_{3027}$ chứa đủ các số $b_0, b_1, \ldots, b_{3k}$. Theo giả thiết quy nạp, trong các số $b_0, b_1, \ldots, b_{3k}$ có ít nhất một số chia hết cho $2^{2k}$.
  Từ đó suy ra, trong các số $a_1, a_2, \ldots, a_{3k+1}$ có ít nhất một số chia hết cho $2^{2k+2}$. Và như thế, trong các số $a_0, a_1, a_2, \ldots, a_{3k+3}$ có ít nhất một số chia hết cho $2^{2k+2}$. Vậy khẳng định đúng với $k+1$.

Theo nguyên lí quy nạp, ta có khẳng định đúng với mọi $1\le k\le 1010$. Ta có điều phải chứng minh.