\( a_n = a_{n-1} + \ant { \sqrt {a_{n-1}} } \)

(*) Следующая задача предлагалась на интернет-олимпиаде NIMO/2012 (National Internet Math Olympiad). Формулировка изменена мной, чтобы выделить интересный факт — бесконечное количество полных квадратов в последовательности.

139. Задана целочисленная последовательность \(
\bigl\{ a_n \bigr\}_{n=1}^{\infty} \) \[
a_1 = 1,
\quad
a_n = a_{n-1} + \ant { \sqrt {a_{n-1}} }
\ (n \geqslant 2) .
\tag {139.1}
\] Докажите, что в этой последовательности бесконечное количество полных квадратов, и определите их вид.

Решение. Вычислим первые элементы последовательности \[
a_n =
\bigl\{ 1, \, 2, \, 3, \, 4, \, 6, \, 8, \, 10, \, 13, \, 16, \, 20, \, 24, \, 28, \, 33,
\, 38, \, 44, \, 50, \, 57, \, 64, \, \ldots
\bigr\} .
\] Зададим другую последовательность \(
\bigl\{ b_k \bigr\}_{k=1}^{\infty} \), которая является подпоследовательностью \( \bigl\{ a_n \bigr\} \), с помощью формулы \(
k \)-го члена \[
b_k = \min\limits_{n \geqslant 1} \bigl( a_n \geqslant k^2 \bigr) ,
\tag {139.2}
\] первые элементы которой равны \[
b_n =
\bigl\{ 1, \, 4, \, 10, \, 16, \, 28, \, 38, \, 50, \, 64, \, \ldots
\bigr\} .
\] Если \( b_k = k^2 \), то очевидно, что \[
b_{k+1} = b_k + 3k .
\tag {139.3}
\] Почти очевидно, что если \( b_k > k^2 \), то \[
b_{k+1} = b_k + 2k .
\tag {139.4}
\] Попытаемся найти следующий полный квадрат в последовательности \(
\bigl\{ b_k \bigr\} \) вида \(
b_{k+m} = (k+m)^2 \), предположив, что \( b_k = k^2 \). Для данного условия должно выполняться равенство \[
b_{k+m} = b_k + 3k + 2(k+1) + 2(k+2) + \ldots + 2(k+m-1) ,
\] \[
(k+m)^2 = k^2 + 3k + (m - 1) (2k + m) , \ ... ,
\] \[
k = m .
\] Значит, если \( b_k = k^2 \), то \( b_{2k} = (2k)^2 \), и других полных квадратов нет.

Ответ: \( 2^{2k} \), где \( k = 0, \, 1, \, 2, \, \ldots \)