Why are sums of powers of 2 able to give all numbers? 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.
 A: 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$.
A: 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.
A: 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$.
A: 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$.
A: 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.
