Prove que todo número natural pode ser representado como uma soma de diversas potências distintas de 2 .
Passo 1
O enunciado pede para provar que todo
pode ser expresso como soma de potências distintas de
. Em outras palavras, mostrar que existem índices inteiros
tais que
A estratégia escolhida é usar indução forte sobre
.
Passo 2
Base da indução:
- Para
basta tomar a soma vazia (não há potências) e convencionamos . - Para
temos imediatamente
que é soma de uma única potência de 2.
Passo 3
Hipótese de indução forte: suponha que todo número natural
com
já possa ser escrito como soma de potências distintas de
. Vamos mostrar que a propriedade vale também para
.
Passo 4
Caso
par. Então
com
. Pela hipótese de indução forte existe uma escrita
com
. Multiplicando ambos os lados por 2 obtemos
onde os expoentes
são todos distintos, provando o caso par.
Passo 5
Caso
ímpar. Escreva
. Como
é par e
, pela hipótese de indução forte existe
com
. Note que, por ser
par, nenhum
pode ser zero (caso contrário a soma seria ímpar). Portanto, ao somar
, obtemos
e
, garantindo que todas as potências são distintas.
Passo 6
Conclusão da indução: cobrimos o caso base e mostramos que, se todo
tem a representação desejada, então
também a tem. Logo, por indução forte, todo
pode ser escrito como soma de potências distintas de
.
Resposta
Demonstrou-se que, para cada
, existe uma soma de potências distintas de
que resulta em
.