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 n\in\mathbb{N} admite uma escrita
n = 2^{e_1} + 2^{e_2} + \cdots + 2^{e_k}
com os expoentes e_1,e_2,\dots,e_k todos distintos. O método mais direto é usar prova por indução forte (ou completa) sobre n.

Passo 2

Base da indução:
Para n=0 basta escolher soma vazia (nenhuma potência de 2), ou então
0 = 0\cdot 2^0
que pode ser vista como não utilizando nenhuma potência positiva. Logo a propriedade vale para n=0.

Passo 3

Passo indutivo (indução forte):
Suponha que todo m com 0 \le m \le k já possa ser escrito como soma de potências distintas de 2. Vamos provar para n = k+1.
  1. Se k+1 é par, escreva k+1 = 2m. Como m \le k, pela hipótese indutiva há
m = 2^{e_1} + 2^{e_2} + \cdots + 2^{e_r}
com e_i distintos. Multiplicando por 2 obtemos
k+1 = 2m = 2^{e_1+1} + 2^{e_2+1} + \cdots + 2^{e_r+1}
onde os expoentes e_i+1 continuam distintos.
2. Se k+1 é ímpar, escreva k+1 = 2m + 1. De novo, m \le k e pela hipótese
m = 2^{e_1} + 2^{e_2} + \cdots + 2^{e_r}\,.
Então
k+1 = 2m + 1 = 2^{e_1+1} + 2^{e_2+1} + \cdots + 2^{e_r+1} + 2^0
e aqui 2^0 não coincide com nenhuma das outras potências, pois todas elas têm expoente \ge1.

Passo 4

Como em ambos os casos ( k+1 par ou ímpar) encontramos uma soma de potências de 2 com expoentes distintos, a propriedade se mantém para n=k+1. Assim, por indução forte, vale para todo n\in\mathbb{N}.

Resposta

Por indução forte concluímos que todo número natural pode ser escrito como soma de potências distintas de 2.

Exercícios relacionados