Matematyka.pl

Zrobimy indukcję ze względu na \(\displaystyle{ n}\).
W ramach pierwszego kroku sprawdzamy wszystko do \(\displaystyle{ n=8}\). Wszystko działa w w miarę oczywisty sposób.

Teraz zakładamy, że wszystkie liczby od \(\displaystyle{ 1}\)do \(\displaystyle{ n-1}\) da się przedstawić w ten sposób.

Zauważmy, że jeśli \(\displaystyle{ 2}\) lub \(\displaystyle{ 3}\) dzieli nam naszą liczbę, to teza zachodzi, bo możemy ją przedstawić w postaci \(\displaystyle{ n=2^{i}3^{j}k}\), a \(\displaystyle{ k<n}\), więc z założenia indukcyjnego da się tak przedstawić, a skoro żaden ze składników w sumie równej \(\displaystyle{ k}\) nie dzieli żadnego innego, to oznacza, że jeśli podzielimy jakiś składnik \(\displaystyle{ 2^{a_{x}}3^{b_{y}}}\) przez jakiś inny, to uzyskamy liczbę niecałkowitą. Jeżeli natomiast pomnożymy obie te liczby przez \(\displaystyle{ 2^{i}3^{j}}\), to przy dzieleniu nam się ten czynnik skróci i i tak liczba nie będzie całkowita.

Zakładamy zatem, że ani \(\displaystyle{ 2}\), ani \(\displaystyle{ 3}\) nie dzieli \(\displaystyle{ n}\).

Niech \(\displaystyle{ 2^{m} < n < 2^{m+1}}\). Ostra nierówność, bo nasza liczba nie jest nawet parzysta. Jako że sprawdziliśmy wystarczająco dużo przypadków początkowych, możemy założyć \(\displaystyle{ m>2}\).

Ponieważ \(\displaystyle{ n}\) nie jest podzielne przez \(\displaystyle{ 3}\), zachodzi:

\(\displaystyle{ n \equiv 2^{m} ( \mod 3)}\) lub \(\displaystyle{ n \equiv 2^{m-1} ( \mod 3)}\).

Bo potęgi dwójki przyjmują na zmianę dwie reszty modulo \(\displaystyle{ 3}\).

Możemy więc zapisać:
W pierwszym przypadku:
\(\displaystyle{ n=3k+2^{m}}\)
W drugim: \(\displaystyle{ n= 3k+ 2^{m-1}}\).
Oczywiście na mocy założenia indukcyjnego \(\displaystyle{ k}\) możemy przedstawić w żądanej postaci. Wystarczy teraz udowodnić, że w żadnym przypadku żaden ze składników występujących w sumie \(\displaystyle{ 3k}\) nie dzieli odpowiedniej potęgi dwójki, i vice versa - potęga dwójki nie dzieli żadnego z tych składników.

Pierwsze zadanie jest prostsze - oczywiście każdy z tych składników podzielny jest przez \(\displaystyle{ 3}\) stojące przed \(\displaystyle{ k}\), więc nie może dzielić potęgi dwójki.

Weźmy drugi przypadek i przypuśćmy teraz, że istnieje taki składnik w sumie \(\displaystyle{ 3k}\), który jest podzielny przez \(\displaystyle{ 2^{m-1}}\). Ponieważ \(\displaystyle{ \nwd(3, 2^{m-1}) = 1}\), taki składnik musi występować w sumie \(\displaystyle{ k}\). W związku z tym:
\(\displaystyle{ n=3(l+q2^{m-1}) + 2^{m-1}> (3q+1)2^{m-1} > 4 \cdot 2^{m-1} = 2^{m+1}}\)
Otrzymaliśmy \(\displaystyle{ n>2^{m+1}}\), co stoi w sprzeczności z definicją \(\displaystyle{ m}\).

W pierwszym przypadku rozumowanie jest analogiczne.

Oznacza to, że udowodniliśmy drugi krok indukcyjny, a zatem na mocy indukcji matematycznej teza jest prawdziwa, co kończy dowód.