Первое решение. Приведём сначала чисто «олимпиадное» решение задачи, принадлежащее С. Конягину: требуемой последовательностью является последовательность 2, $2^23$, $2^23^25$, $2^23^25^27$, $\ldots$, $2^23^2\ldots p_{n-1}^2p_n$, $\ldots$, где $p_n$ — $n$-е простое число. Никакая сумма чисел, составленная из членов этой последовательности, не является степенью натурального числа, так как любая из таких сумм делится на $p_k$, где $k$ — наименьший из номеров членов последовательности, входящих в эту сумму, и не делится на $p_k^2$.
Второе решение. Додуматься до примера из первого решения довольно трудно. Поэтому мы покажем, как можно доказать существование последовательности с требуемыми свойствами, не выписывая самой последовательности («чистая» теорема существования).
В этом решении мы будем пользоваться понятием плотности множества.
Определение. Пусть $A\subset\mathbb N$ и $\nu_n(A)$ — число элементов множества $A$, не превосходящих данного числа $n\in\mathbb N$. Если существует предел последовательности $\lim\limits_{n\to\infty}\dfrac{\nu_n(A)}n=d(A)$, то число $d(A)$ называется плотностью множества $A$.
Например, плотность арифметической прогрессии $A=\{a+dn\mid n\in\mathbb N\}$ равна $\dfrac1d$, а геометрической — $A=\{bq^n\mid n\in\mathbb N\}$ равна 0. Равна нулю и плотность любого конечного множества.
Легко доказать, что плотность объединения нескольких множеств нулевой плотности также равна нулю и что плотность множества $A\pm c$, полученного из множества $A$ нулевой плотности сдвигом на $\pm c$ ($A\pm c=\{a\pm c\mid a\in A\}$), равна нулю.
Докажем теперь следующее утверждение.
Лемма. Если $d(A)=0$, то существует такое бесконечное множество $B$, что никакая сумма попарно различных чисел из $B$ не принадлежит $A$ и $B\cap A=\varnothing$.
Доказательство. Будем строить множество $B$ по индукции. Так как $d(A)=0$, существует натуральное число $b_1\notin A$. Это и будет первый элемент множества $B$. Пусть выбраны $k$ элементов множества $B$: $b_1$, $b_2$, $\ldots$, $b_k$. Обозначим через $r_1$, $r_2$, $\ldots$, $r_s$ всевозможные суммы, образованные из этих чисел, и рассмотрим множества $A_i=A-r_i$ ($i=1$, 2, $\ldots$, $s$). Каждое из них имеет нулевую плотность, и поэтому их объединение $V=A_1\cup A_2\cup\ldots\cup A_s$ также имеет нулевую плотность. Следовательно, существует натуральное число $b_{k+1}$, не принадлежащее множествам $V$ и $A$. Ясно, что никакая из сумм чисел $b_1$, $b_2$, $\ldots$, $b_{k+1}$ не принадлежит множеству $A$. Существование множества $B$ доказано.
В силу леммы для утвердительного ответа на вопрос задачи достаточно доказать, что множество $S=\{a^k\mid a\ge1{,}~k\ge2\}$ всевозможных степеней натуральных чисел имеет нулевую плотность.
Оценим количество $\nu_n(S)$ степеней, не превосходящих числа $n$. Если $a^k\le n$, то $a\le\!\sqrt[\scriptstyle k~]{n}$. Поэтому натуральных чисел, $k$-я степень которых не превосходит $n$, имеется не более, чем $[\!\sqrt[\scriptstyle k~]{n}]$, где $[x]$ — целая часть числа $x$. В частности, при $k\gt m=[\log_2n]$ существует только одно такое число — единица. Следовательно,
$$
\nu_n(S)\le\dfrac{[\sqrt n]+[\!\sqrt[\scriptstyle3~]n]+\ldots+[\!\sqrt[\scriptstyle m~]n]}n\le\dfrac{\sqrt n\log_2n}n=\dfrac{\log_2n}{\sqrt n}.
$$
Переходя к пределу при $n\to\infty$, получим
$$
d(S)=\lim\limits_{n\to\infty}\nu_n(S)\le\lim\limits_{n\to\infty}\dfrac{\log_2n}{\sqrt n}=0.
$$
