[Teoria liczb] Ciąg i potęgi

[Swistak]

Udowodnij, że istnieje nieskończony ciąg liczb naturalnych, taki, że żadna liczba w tym ciągu ani żadna z sum wybranych elementów nie jest potęgą liczby naturalnej.
Od razu powiem, że istnieje dowód zarówno konstruktywny jak i niekonstruktywny, jednak zachęcam do znalezienia niekonstruktywnego, bo jest n razy fajniejszy .

[TomciO]

Ukryta treść:    

Zauważmy, że dla dowolnego skończonego zbioru \(\displaystyle{ A}\), który ma tą własność, że suma żadnego jego podzbioru nie jest potęgą da się dobrać \(\displaystyle{ x \in \mathbb{N}}\) tak aby zbiór \(\displaystyle{ A \cup \{ x \}}\) dalej miał tą własność. Rzeczywiście, wystarczy zadbać tylko o to aby sumy tych podzbiorów co zawierają \(\displaystyle{ x}\) nie były potęgami, niech \(\displaystyle{ s_1, s_2, \ldots, s_k}\) oznaczają sumy wszystkich podzbiorów zbioru \(\displaystyle{ A}\). Dobierzmy \(\displaystyle{ k}\) dużych liczb pierwszych \(\displaystyle{ p_1 , p_2, \ldots, p_k}\), dużych w tym sensie, że są większe niż wszystkie liczby \(\displaystyle{ s_i}\). Z chińskiego twierdzenia o resztach istnieje \(\displaystyle{ x \in \mathbb{N}}\), które spełnia \(\displaystyle{ x + s_i \equiv p_i \pmod{p_i^2}}\). Teraz jest jasne, że \(\displaystyle{ x+s_i}\) nie jest potęgą liczby naturalnej dla \(\displaystyle{ i=1, 2, \ldots, k}\) co więcej w ten sam sposób możemy zagwarantować to, że \(\displaystyle{ x}\) również nie jest potęgą.
Mając powyższy fakt wystarczy przyjąć \(\displaystyle{ a_1 = 2}\) a następnie konstruować ciąg indukcyjnie za pomocą podanej wyżej własności.

Dowód niekonstruktywny rzeczywiście powinien być ciekawy

[Swistak]

Już trochę czasu minęło, więc przedstawię swój niekonstruktywny dowód.

Ukryta treść:    

Weźmy sobie jakiś skończony zbiór A o zadanej własności o mocy \(\displaystyle{ k}\). Udowodnimy, że da się do tego zbioru dołożyć jakąś liczbę, taką, że w tym zbiorze nadal żaden podzbiór nie będzie się sumować do potęgi liczby naturalnej o wykładniku większym niż 1.
Dołóżmy sobie jakąś liczbę \(\displaystyle{ n}\) (niech będzie większa od reszty) i rozpatrzmy możliwe sumy. Kurczę, niestety jakaś jest tą potęgą.
Weźmy sobie w takim razie \(\displaystyle{ n+1}\). No kurczę, znowu suma jakiegoś podzbioru jest potęgą.
...
Dołóżmy teraz \(\displaystyle{ n+S}\), gdzie S jest takie duże, że ojej i jeszcze trochę. Znowu trafiliśmy w jakąś potęgę.
Jednak popatrzmy, co musi być spełnione, aby takie coś było możliwe? Nietrudno zauważyć, żeby to było spełnione zawsze od pewnego miejsca, to nie może zachodzić \(\displaystyle{ \lim_{m \to \infty} \frac{k(m)}{m}<\frac{1}{2^n}}\), gdzie \(\displaystyle{ k(m)}\) jest to liczba potęg liczby naturalnych mniejszych od m.
Zauważmy, że liczba potęg liczb naturalnych o wykładniku większym od 1 nie przekracza liczby kwadratów mniejszych od m, sześcianów mniejszych od m, 4-tych potęg mniejszych od m, ..., \(\displaystyle{ \log_2 m}\) potęg mniejszych od m. Jest tak dlatego, że jedyną liczbą naturalną, która podniesiona do potęgi większej od \(\displaystyle{ log_2 m}\) jest mniejsza od m jest 1, a to znajduje się np. wśród kwadratów. Wiedząc to możemy \(\displaystyle{ k(m)}\) oszacować z góry przez \(\displaystyle{ \sqrt{m}+\sqrt[3]{m}+...+\sqrt[\log_2 \ m]{m}<\sqrt{m} \ \log_2 m}\), a przecież \(\displaystyle{ \lim_{m \to \infty} \frac{\sqrt{m} \ \log_2 \ m}{m}=0}\), co daje nam sprzeczność. c.b.d.u.