Arithmetic Sequence

Bài toán (China 1991) 

Cho dãy số $(u_n)$ nguyên thỏa mãn $u_{n+2}=u_{n+1}^2-u_n$ với mọi $n$ tự nhiên. Gỉa sử $u_0=39,u_1=45$. Chứng minh có vô hạn số hạng của dãy $(u_n)$ chia hết cho $1986$.

Lời giải :

Gọi $r_n$ là số dư của $u_n$ khi chia cho $1986$ ứng với mỗi $n$. Ta chứng minh dãy $(r_n)$ tuần hoàn.

Xét dãy gồm các bộ số dư :

$$(r_1,r_2),(r_2,r_3),...,(r_m,r_{m+1}),...$$

Dãy trên có vô số số hạng mà số bộ khác nhau là hữu hạn vì $r_i\in \left\{0,1,2,...,1985\right\}$. Như vậy theo nguyên lí Dirichlet, sẽ tồn tại hai bộ trùng nhau. Tức là tồn tại $k,m$ nguyên dương :

$$(r_{m+1},r_{m+2})=(r_{m+k+1},r_{m+k+2})$$

Từ đó :

$$r_m=r_{m+1}^2-r_{m+2}=r_{m+k+1}^2-r_{m+k+2}=r_{m+k}$$

$$r_{m-1}=r_m^2-r_{m+1}=r_{m+k}^2-r_{m+k+1}=r_{m+k-1}$$

…

$$r_1=r_2^2-r_3=r_{k+2}^2-r_{k+3}=r_{k+1}$$

Tức là ta đã được :

$$(r_1,r_2)=(r_{k+1},r_{k+2})$$

Từ đó dựa vào công thức xác định dãy, ta thu được :

$$r_n=r_{n+k},\forall n=0,1,\mathrm{2...}$$

Hơn nữa ta có $u_2=45^2-39=1986$ nên sẽ tồn tại vô hạn số hạng của dãy $(u_n)$ chia hết cho $1986$.