Skip to content
Quantoros

Prove every nonnegative integer is a unique sum of distinct powers of two.

Quant ResearchLevel: IntermediateBinary representation

Prove every nonnegative integer is a unique sum of distinct powers of two.

Hints
  • Use division with remainder for construction.
  • Compare the lowest bit where two proposed representations differ.

Answer

Existence: repeatedly divide by 2 and record remainders 0 or 1. For uniqueness, the lowest differing bit would make the difference an odd multiple of its power of 2 while all higher bits contribute even multiples, impossible. Zero uses the empty sum.

Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial

Related questions