Exercício 0.2 Prove que todo número natural pode ser escrito como soma de potências distintas de 2.
Passo 1
O enunciado pede para mostrar que qualquer
admite uma escrita
com os expoentes
todos distintos. O método mais direto é usar prova por indução forte (ou completa) sobre
.
Passo 2
Base da indução:
Para basta escolher soma vazia (nenhuma potência de
), ou então
Para
que pode ser vista como não utilizando nenhuma potência positiva. Logo a propriedade vale para
.
Passo 3
Passo indutivo (indução forte):
Suponha que todo com
já possa ser escrito como soma de potências distintas de
. Vamos provar para
.
Suponha que todo
- Se
é par, escreva . Como , pela hipótese indutiva há
com
distintos. Multiplicando por
obtemos
onde os expoentes
continuam distintos.
2. Se é ímpar, escreva
. De novo,
e pela hipótese
2. Se
Então
e aqui
não coincide com nenhuma das outras potências, pois todas elas têm expoente
.
Passo 4
Como em ambos os casos (
par ou ímpar) encontramos uma soma de potências de
com expoentes distintos, a propriedade se mantém para
. Assim, por indução forte, vale para todo
.
Resposta
Por indução forte concluímos que todo número natural pode ser escrito como soma de potências distintas de
.