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