Why are sums of powers of 2 able to give all numbers?

Question

It is known that

If we sum up a combination of numbers that are positive powers of 2(starting from 0 to infinity), we can get any number possible.

(Correct me if this is wrong).

Can anyone give a proof and explain how this works? Please try to make it understandable.

Answer 1

You're probably familiar with the idea of "base $10$" representation of integers. That's our normal decimal system. We write $275$ to stand for $2(10^2)+7(10^1)+5(10^0)$. In base $10$, the digits $0,1,\ldots,9$ occur as multipliers of powers of $10$, and the products are added up to give the number in question.

The same sort of thing is possible for any integral base $b>1$. For example, if you take $b=7$, then every positive integer can be uniquely expressed as a sum of multiples of powers of $7$, where the multipliers are integers in the range $0,1,\ldots,6$ (the highest possible digit is always one less than the base--compare the familiar base $10$ with digits $0-9$ mentioned above).

So in particular, if you take $b=2$, then the multipliers (i.e., digits) can only be in the range $0-1$.

Note that you can always leave out of the sum any term whose multipler (digit) is zero, because it contributes nothing (adds zero).

In base $2$, that leaves only terms whose multiplier (digit) is $1$, because the digit can only be $0$ or $1$ to begin with.

What's left is a sum of terms of the form $1\cdot 2^k$. Such a term is just $2^k$.

What I haven't shown is why it is possible to do this with any base. (In fact, as it turns out, it isn't even necessary to use a constant base. But that's a much more general representation.) It ultimately depends on the existence of the division algorithm: Given positive integers $p$ and $q$, there are unique integers $n$ and $r$ such that $p=nq+r$ with $0\leq r<q$.

Answer 2

The number $7$ is the first number (other than $1$) that is not the sum of two powers of $2$. However it is the sum of three powers of $2$, $$7=2^2+2^1+2^0$$ If we allow sums of any combination of powers of $2$, then yes, we can get any natural number. (That is what makes binary representations possible.) You can get an easy proof by strong induction:

• Every natural number $\leq 2^1$ is a sum of some number of powers of $2$

• Suppose that every natural number $\leq 2^k$ is a sum of some number of powers of $2$. Then every natural number $n\leq 2^{k+1}$ either already satisfies $n\leq 2^k$, in which case it has an expression as a sum of powers of $2$ by the inductive hypothesis, or satisfies $2^k<n\leq 2^{k+1}$, in which case $(n-2^k)\leq 2^k$ has an expression as a sum of powers of $2$ by the inductive hypothesis and therefore so does $n$.

You can strengthen this argument slightly to show that in fact every natural number is a sum of some number of powers of $2$ without repetition (i.e., any given power of $2$ is used at most once in the sum). This corresponds to showing that a binary representation needs only digits $0$ and $1$.

It's also true that, once we restrict to looking at sums of powers of $2$ without repetition, the powers of $2$ that add up to a given natural number are uniquely specified; this corresponds to showing that a given natural number has exactly one binary representation using only digits $0$ and $1$.

Answer 3

Here's an example, which can be easily expanded to the general case. Let's say we want to write $21$ as the sum of distinct powers of two. ("Distinct" meaning that they're all different.)

Well, if we drop the distinctness condition, it's easy:

$21=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1$

Let's try to clean this up a bit. We don't need more than one $1$, because we can do this:

$21=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1\\ \phantom{21}=(1+1)+(1+1)+(1+1)+(1+1)+(1+1)+(1+1)+(1+1)+(1+1)+(1+1)+(1+1)+1\\ \phantom{21}=2+2+2+2+2+2+2+2+2+2+1$

Similarly, we don't need more than one $2$, because we can do this:

$21=2+2+2+2+2+2+2+2+2+2+1\\ \phantom{21}=(2+2)+(2+2)+(2+2)+(2+2)+(2+2)+1\\ \phantom{21}=4+4+4+4+4+1$

And we don't need more than one $4$:

$21=4+4+4+4+4+1\\ \phantom{21}=(4+4)+(4+4)+4+1\\ \phantom{21}=8+8+4+1$

And finally:

$21=8+8+4+1\\ \phantom{21}=(8+8)+4+1\\ \phantom{21}=16+4+1$

Basically, we start with a bunch of ones, and then "collapse" them until all powers of two are different from each other.

Answer 4

Given $n,q \in \mathbb{N}$.

Consider the recursion

$$ \begin{array}{rcl} n_0 &=& n,\\ m_p &=& \lfloor \log_q n_p \rfloor \in \mathbb{N},\\ n_{p+1} &=& n_{p} - q^{\displaystyle m_p} \in \mathbb{N}. \end{array} $$

Then we obtain

$$ \exists k : m_k = 0 \Longrightarrow n = \sum_{\ell=0}^k q^{m_\ell}. $$

What we need to prove that there always exists a $k$ such that $m_k = 0$.

Try to proof this. (I will add the proof later to the post)

By setting $q=2$, you have the answer to your question.

But it generally holds for and $q \ge 2$.

Answer 5

Suppose that the integer $m$ can be written as a binary number. Find the rightmost $0$ bit in that binary number. That is, $m$ looks like $$ m=\overbrace{\text{????????}}^{\substack{\text{some sequence}\\\text{of $0$s and $1$s}}}\overbrace{0111111}^{\substack{\text{$1$ zero and}\\\text{ $n$ ones}}} $$ Then $m+1$ looks like $$ m+1=\overbrace{\text{????????}}^{\substack{\text{same sequence}\\\text{of $0$s and $1$s}}}\overbrace{1000000}^{\substack{\text{$1$ one and}\\\text{ $n$ zeros}}} $$ This is justified by the formula for the sum of a geometric series, $$ \sum_{k=0}^{n-1}2^k=\frac{2^n-1}{2-1}=2^n-1 $$ That is, the sequence of $1$ zero followed by $n$ ones represents $2^n-1$.

The $1$ one followed by $n$ zeros is the binary representation for $2^n$.

The preceding sequence of $0$s and $1$s adds the same to both numbers.

Thus, if $m$ can be written as a binary number, $m+1$ can be written as a binary number. Since $0$ can be written as a binary number, all integers can be written as a binary number.