Arithmetic Sequence

Bài toán (International Mathematical Olympiad Shortlist 1988)

Cho dãy số nguyên $(a_n)$ xác định bởi :

$$a_0=0,a_1=1,a_{n+2}=2a_{n+1}+a_n$$.

Chứng minh rằng $2^k\mid a_n$ khi và chỉ khi $2^k\mid n$.

Lời giải :

Bổ đề : Cho dãy số $(x_n)$ xác định bởi $x_1=a,x_2=b$ và :

$$x_{n+2}=b{x}_{n+1}+a{x}_n$$.

Khi đó với $m$ nguyên dương bất kỳ, ta có :

$$x_{m+n}=x_n{x}_{m+1}+x_{n-1}{x}_m(\ast )$$

Chứng minh bổ đề :

Ta chứng minh bằng quy nạp theo $m$, với $m=1$ thì hiển nhiên. Gỉa sử $(\ast )$ đúng với $m$ và $m-1$. Xét với $m+1$ :

$x_{m+n+1}$$=b{x}_{m+n}+a{x}_{m+n-1}$$=b\left(x_n{x}_{m+1}+x_{n-1}{x}_m\right)+a\left(x_n{x}_m+x_{n-1}{x}_{m-1}\right)$$=x_n(b{x}_{m+1}+a{x}_m)+x_{n-1}(b{x}_m+a{x}_{m-1})$$=x_n{x}_{m+2}+x_{n-1}{x}_{m+1}$

Quy nạp hoàn tất, như vậy ta có đẳng thức $(\ast )$.

Kết quả này là một kết quả quan trọng được dùng cho nhiều bài toán.

Trở lại bài toán :

Ta chọn $m=n$ trong $(\ast )$ thì ta được :

$$x_{2n}=x_n\left(x_{n-1}+x_{n+1}\right)=2x_n(x_n+x_{n-1})(\ast \ast )$$

Bằng quy nạp ta chứng minh được $a_{2n+1}$ lẻ và $a_{2n}$ chẵn. Như vậy $x_n+x_{n-1}$ lẻ.

Nếu $2^k\mid a_n$. Đặt $n=2^m.t$ với $t$ lẻ. Sử dụng $(\ast )$ ta được :

$$2^k\mid a_n=a_{2^m.t}\Rightarrow 2^{k-1}\mid a_{2^{m-1}.t}\Rightarrow 2^{k-2}\mid a_{2^{m-2}.t}$$

Nếu $k>m$ thì cứ tiếp tục quá trình này, ta được $2^{k-m}\mid a_t$ và điều này vô lí vì $a_t$ lẻ (do $t$ lẻ)

Vậy phải có $k\le m$, suy ra $2^k\mid 2^m.t=n$.

Nếu $2^k\mid n$. Đặt $n=2^k.t$ và cũng sử dụng $(\ast )$ ta có :

$2^0\mid a_t$$\Rightarrow 2^1\mid a_{2t}$$\Rightarrow 2^2\mid a_{2^2.t}$$\Rightarrow ...$$\Rightarrow 2^k\mid a_{2^k.t}$$=a_n$

Bài toán hoàn tất.