Arithmetic Sequence

Bài toán (AMM, Problem E2619, Thomas C.Brown)

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

$$a_1=1,a_{n+1}=a_n+\lfloor \sqrt{a_n}\rfloor$$

Chứng minh rằng $a_n$ là số chính phương khi và chỉ khi $n=2^k+k-2$ với $k$ là số tự nhiên.

Lời giải :

Quan sát một số số hạng đầu tiên :

$a_1$$=1,a_2$$=2,a_3$$=3,a_4$$=4,a_5$$=6,a_7$$=10,a_8$$=13,a_9$$=16,a_{10}$$=20,a_{11}$$=24,a_{12}$$=28,a_{13}$$=33,a_{14}$$=38,a_{15}$$=44,a_{16}$$=50,a_{17}$$=57,a_{18}$$=64,...$

Ta thấy các số hạng chính phương là $a_1=1^2,a_4=2^2,a_9=4^2,a_{18}=8^2,...$ và một số hạng chính phương sẽ có căn gấp đôi căn của số hạng chính phương kế trước nó.

Như vậy ta đi chứng minh nếu $a_k=m^2$ thì số hạng chính phương liền sau của nó bằng $(2m{)}^2$.

Ta tính được :

$$a_{k+1}=a_{k+2.0+1}=m^2+m=(m+0{)}^2+(m-0)$$

$$a_{k+2}=a_{k+2.1}=m^2+2m=(m+1{)}^2-1$$

$$a_{k+3}=a_{k+2.1+1}=m^2+3m=(m+1{)}^2+(m-1)$$

$$a_{k+4}=a_{k+2.2}=m^2+4m+1=(m+2{)}^2-3$$

$$a_{k+5}=a_{k+2.2+1}=m^2+5m+2=(m+2{)}^2+(m-2)$$

$$a_{k+6}=a_{k+2.3}=m^2+6m+4=(m+3{)}^2-5$$

$$a_{k+7}=a_{k+2.3+1}=m^2+7m+6=(m+3{)}^2+(m-3)$$

$$a_{k+8}=a_{k+2.4}=m^2+8m+9=(m+4{)}^2-9$$

Qua quy luật của các số hạng trên, ta chứng minh bằng quy nạp :

$$a_{k+2s}=(m+s{)}^2-(2s-1),a_{k+2s+1}=(m+s{)}^2+(m-s)(\ast )$$

Gỉa sử điều này là đúng. Ta xét với $s+1$.

$a_{k+2s+2}$$=a_{k+2s+1}+\lfloor \sqrt{a_{k+2s+1}}\rfloor$$=(m+s{)}^2+(m-s)+\lfloor \sqrt{(m+s{)}^2+(m-s)}\rfloor$$=(m+s{)}^2+(m-s)+(m+s)$$=(m+s+1{)}^2-2(s+1)+1$

$a_{k+2s+3}$$=a_{k+2s+2}+\lfloor \sqrt{a_{k+2s+2}}\rfloor$$=(m+s+1{)}^2-2s-1+\lfloor \sqrt{(m+s+1{)}^2-2s-1}\rfloor$$=(m+s+1{)}^2-2s-1+(m+s)$$=(m+s+1{)}^2+(m-s-1)$

Vậy theo nguyên lý quy nạp ta được $(\ast )$. Rõ ràng $a_{k+2s}$ không thể chính phương vì :

$$(m+s-1{)}^2<(m+s{)}^2-2s+1<(m+s{)}^2$$

Và nếu $s\le m$ thì $(m+s{)}^2\le (m+s{)}^2+(m-s)\le (m+s+1{)}^2$, suy ra $a_{k+2s+1}$ chỉ là số chính phương nếu $s=m$ và khi đó $a_{k+2m+1}=(2m{)}^2(\ast \ast )$.

Còn nếu $s>m$ thì $a_{k+2s+1}=(m+s{)}^2+(m-s)>(2m{)}^2=a_{k+2m+1}$ nên $a_{k+2s+1}$ không thể là số chính phương kế tiếp sau $a_k$.

Như vậy một số hạng chính phương sẽ có căn gấp đôi căn của số hạng chính phương kế trước nó. Hơn nữa ta có $$a_1=1^2$$ nên bằng quy nạp ta có thể chỉ ra được các số hạng chính phương của dãy đều là một lũy thừa bậc chẵn của $$2$$.

Bây giờ ta trở lại với $n=2^k+k-2$.

Chọn $k=1$ ta được $a_1=1=2^0$. Chọn $k=2$ ta được $a_2=4=(2^1{)}^2$. Chọn $k=3$ ta được $a_3=16=(2^2{)}^2$. Chọn $k=4$ ta được $a_{18}=2^6=(2^3{)}^2$…

Ta quy nạp :

$$a_{2^k+k-2}=2^{2(k-1)}$$

Gỉa sử điều này là đúng. Xét với $k+1$, ta cần chứng minh :

$$a_{2^{k+1}+(k+1)-2}=2^{2k}$$

Điều này là đúng nếu trong $(\ast \ast )$ ta chọn thay $k$ bởi $2^k+k-2$ và chọn $m=2^{k-1}$, lúc đó :

$$a_{2^k+k-2+2(2^{k-1})+1}=(2.2^{k-1}{)}^2=2^{2k}\Rightarrow a_{2^{k+1}+(k+1)-2}=2^{2k}$$

Ta hoàn tất bài toán.