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 n\in\mathbb{N} pode ser expresso como soma de potências distintas de 2. Em outras palavras, mostrar que existem índices inteiros k_1<k_2<\cdots<k_m tais que
n = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_m}.
A estratégia escolhida é usar indução forte sobre n.

Passo 2

Base da indução:
  1. Para n=0 basta tomar a soma vazia (não há potências) e convencionamos 0=\sum_{\emptyset}2^k.
  2. Para n=1 temos imediatamente
1 = 2^0,
que é soma de uma única potência de 2.

Passo 3

Hipótese de indução forte: suponha que todo número natural k com 0\le k<n já possa ser escrito como soma de potências distintas de 2. Vamos mostrar que a propriedade vale também para n.

Passo 4

Caso n par. Então n=2m com m<n. Pela hipótese de indução forte existe uma escrita
m = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_r},
com a_1<\cdots<a_r. Multiplicando ambos os lados por 2 obtemos
n = 2m = 2\bigl(2^{a_1} + 2^{a_2} + \cdots + 2^{a_r}\bigr) = 2^{a_1+1} + 2^{a_2+1} + \cdots + 2^{a_r+1},
onde os expoentes a_i+1 são todos distintos, provando o caso par.

Passo 5

Caso n ímpar. Escreva n = (n-1) + 1. Como n-1 é par e n-1<n, pela hipótese de indução forte existe
n-1 = 2^{b_1} + 2^{b_2} + \cdots + 2^{b_s},
com b_1<\cdots<b_s. Note que, por ser n-1 par, nenhum b_i pode ser zero (caso contrário a soma seria ímpar). Portanto, ao somar 1=2^0, obtemos
n = 2^0 + 2^{b_1} + 2^{b_2} + \cdots + 2^{b_s},
e 0<b_1<\cdots<b_s, 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 k<n tem a representação desejada, então n também a tem. Logo, por indução forte, todo n\in\mathbb{N} pode ser escrito como soma de potências distintas de 2.

Resposta

Demonstrou-se que, para cada n\in\mathbb{N}, existe uma soma de potências distintas de 2 que resulta em n.

Exercícios relacionados