Bài toán 24.[IMO Longlist, 1988] Cho dãy số nguyên $\left(a_n\right)$ được xác định bởi $a_0=0, a_1=1$ và $a_{n+2}=2a_{n+1}+a_{n}$ với mọi $n\in \mathbb{N}$. Với mỗi số tự nhiên $k$ cho trước, chứng minh rằng $a_n$ chia hết cho $2^k$ khi và chỉ khi $n$ chia hết cho $2^k$.

Bài toán 24.[IMO Longlist, 1988] Cho dãy số nguyên $\left(a_n\right)$ được xác định bởi $a_0=0, a_1=1$ và $a_{n+2}=2a_{n+1}+a_{n}$ với mọi $n\in \mathbb{N}$. Với mỗi số tự nhiên $k$ cho trước, chứng minh rằng $a_n$ chia hết cho $2^k$ khi và chỉ khi $n$ chia hết cho $2^k$.

Lời giải

Rõ ràng khẳng định đúng với $k=0$. Do đó, ta chỉ cần xét trường hợp $k > 0$.
Bằng quy nạp, ta dễ dàng chứng minh được $a_n\equiv 1 \left(\bmod 4\right)$ với mọi số tự nhiên lẻ $n$. Ngoài ra, ta cũng tìm được công thức tổng quát cho các số hạng của dãy $\left(a_n\right)$ là $$a_n=\dfrac{{x_1}^n-{x_2}^n}{2\sqrt{2}},$$ trong đó $x_1=1+\sqrt{2}$ và $x_2=1-\sqrt{2}$. Dễ thấy $$a_{2n}=\dfrac{{x_1}^{2n}-{x_2}^{2n}}{2\sqrt{2}}=\dfrac{\left({x_1}^n-{x_2}^n\right)\left({x_1}^n+{x_2}^n\right)}{2\sqrt{2}}=a_n\left({x_1}^n+{x_2}^n\right), \forall n \in \mathbb{N}.\tag{1}$$ Bây giờ, ta giả sử tồn tại một số nguyên dương $n$ sao cho $a_n$ chia hết cho $2^k$. Khi đó, rõ ràng $n$ phải là số chẵn. Đặt $n=2^mt$ với $m, t$ là các số nguyên dương và $t$ lẻ. Theo $(1)$, ta có $$\begin{align*} a_n&=a_{2^{m}t}=a_{2^{m-1}t}\left({x_1}^{2^{m-1}t}-{x_2}^{2^{m-2}t}\right)\\ &=\cdots=a_t\left({x_1}^{2^{m-1}t}-{x_2}^{2^{m-1}t}\right)\cdots \left({x_1}^{2t}+{x_2}^{2t}\right)\left({x_1}^t+{x_2}^t\right). \end{align*}$$ Mặt khác, ta chú ý rằng, với mọi $\ell$ nguyên dương thì $$x_1^{\ell}+x_2^{\ell}=2\left(C_{\ell}^0+2C_{\ell}^2+2^2C_{\ell}^4+\cdots\right)=2+2^2C_{\ell}^2+2^3C_{\ell}^4+\cdots$$ chia hết cho $2$ nhưng không chia hết cho $4$. Từ đó suy ra $v_2\left(a_n\right)=m$.
Vì $a_n$ chia hết cho $2^k$ nên $m\ge k$. Do đó $n$ chia hết cho $2^k$. Ta có điều phải chứng minh.