Positive integers expressable as sums of powers of 2 I need to prove that any positive integer is expressable as
$$x=2^{j_0}+2^{j_1}+2^{j_2}+...+2^{j_m}$$
where $m\ge 0$ and $0\le j_0\lt j_1\lt j_2\lt ... \lt j_m. $
I think I get the gist of the proof; what I mean is I think I intuitively understand what is happening here, but looking for verification, either a more simplistic argument or proper rigor.
I start by saying a positive integer is expressable as an even or odd integer.  So, a positive integer, $x=2k$ or $x=2k+1$ for some positive integer $k$.  If $x$ is odd, then we can write $1=2^0$.  Now, an integer $k$ is also expressable as an even or odd integer.  Thus we now have $2^2=4$ possibilities; if $x$ is even;
$$x=2k=2(2k_1)=2^2k_1$$
$$x=2k=2(2k_1+1)=2^2k_1+2^1$$
if $x$ is odd;
$$x=2k+1=2(2k_1)+1=2^2k_1+2^0$$
$$x=2k+1=2(2k_1+1)+1=2^2k_1+2^1+2^0$$
it is clear that $k>k_1$ since $k=2k_1$.  Now we repeat the process with $k_1=2k_2$ or $k_1=2k_2+1$ and eventually, $k_n=2k_{n+1}$ or $k_n=2k_{n+1}+1$.  Since $x$ is a positive integer, $k_i$ is positive for all $i=1,2,...,n$ and thus the larger the $i$, the smaller the $k_i$.  This process eventually terminates since $k_i>0$ and thus $k_n=1$
Now how do I simplify this argument, assuming it's correct.   If it is not correct,, how do I repair it or make it more rigorous?
 A: We can do it by (strong) induction. Let $P(x)$ be the assertion that $x$ is a sum of $0$ or more distinct powers of $2$. The number $0$ is a sum of $0$ or more distinct powers of $2$. So $P(0)$ holds. 
Suppose that $P(k)$ is true  for all $k\lt x$. We show that $P(x)$ is true.  Let $2^p$ be the largest power of $2$ which is $\le x$. Then $x-2^p \lt 2^{p-1}$. By the induction hypothesis, $x-2^p$ is expressible as a sum of $0$ or more distinct powers of $2$. All these powers of $2$ are $\lt 2^p$, since $x-2^p\lt 2^p$. It follows that $x=2^p$ plus a sum of $0$ or more distinct powers of $2$ that are less than $2^p$. So $x$ is a sum of distinct powers of $2$. 
A: Much more generally,
you can prove this:
Let $(b_k)_{k=1}^{\infty}$
be a sequence of integers such that
each $b_k \ge 2$
and let
$B_0 = 1$
and
$B_k = \prod_{j=1}^k b_j$
for $k \ge 1$.
Then every positive integer
$n$ can be represented uniquely
in the form
$n = \sum_{k=0}^{D(n)} d_kB_k$
where
$D(n)$ is a positive integer that depends on $n$
and
the $d_k$ are integers such that
$0 \le d_k < b_{k+1}$.
If all the $b_k$ are equal to $b$,
this gives the 
standard representation in base $b$.
If $b_k = k+1$,
this the "factorial" representation.
There is a converse to this:
If $B_k$ is an increasing sequence
of positive integers
with $B_1 \ge 2$
and $\frac{B_{k+1}}{B_k} \ge 2$
then every positive integer $n$
can be represented
in the form
$n = \sum_{k=0}^{D(n)} d_kB_k$
with $d_k$ integers such that
$0 \le d_k < \frac{B_{k+1}}{B_k}$
and the representation is unique
if and only if
$B_k 
$
divides $B_{k+1}$
for all $k$.
A: This is just the expression of $x$ as a binary (base $2$) number, isn't it?
A: As you say, $x=2k$ or $x=2k+1$. Now, $k<x$ and so, by induction, $k$ can be expressed as a sum of distinct powers of $2$. Then $2k$ can also be so expressed. If $x=2k$, we're done. If $x=2k+1$, then $x=2k+2^0$, and we're done, because $2^0$ does not appear in the expression of $2k$.
A: For a variation, we can use contradiction.
Assume there is a set of positive integers than cannot be expressed as the sum of distinct powers of two. Since the positive integers are well-ordered, there must be a smallest one. Call that one $x$.
Now, subtract from $x$ the largest power of two that is still smaller than $x$. Call this number $y$.
$y = x-2^N$
If $y$ is expressible as a sum of distinct powers, then $x = y + 2^N$, contradicting our assumption. We are not in danger of $2^N$ already appearing in $y$ since $y$ must be smaller than $2^N$. If this wasn't the case, $2^N$ would be smaller than $x/2$ and thus not be the largest power of two less than $x$).  Therefore, $y$ cannot be expressed as a sum of distinct powers of two.
But, $y$ is smaller than $x$, contradicting our assumption that $x$ was the smallest example. Our only possible escape is to set $y=0$, since $0$ isn't a positive integer, thus avoiding the "smallest example" part contradiction. However, this means that $x=2^N$, which obviously contradicts the "not a sum of powers of two" assumption.
Since our assumption leads to nothing but contradictions, it must be false. All numbers are expressible as the sum of distinct powers of two.
A: Proof by Contradiction. Assume $n$ can be written as the sum of distinct powers
of 2 in two different ways. Find the smallest powers of $2$ where the two ways disagree, say
$2^a$ and $2^b$. Assume, WLOG than $a < b$. Subtract all of powers of $2$ that are smaller than $2^a$
From both ways, producing a (possibly smaller) number that is the sum of distinct powers of
$2$ in two different ways. Divide both numbers by $2^a$ producing a (possibly smaller) number
that is the sum of distinct powers of $2$ in two different ways. The way that had $2^a$ as a
power now has $2^0 = 1$ as a power and is therefore odd, but the other way is even. Thus
they cannot be equal, which is a contradiction.
A: Theorem: any non-negative integer is a sum of 0 or more distinct powers of 2.
Proof: By the well-odering principle. Assume there is a set, $C$, of positive integers that can not be expressed as a sum of 0 or more powers of 2. Since $C$ is a subset of the positive integers, by the well-ordering principle, there must be a smallest element, $m$, in C.
It's clear that 0 is the sum of 0 powers of 2, so $m>0$.
Now, let's subtract from $m$ the largest power of two, $2^n$, that is still smaller than $m$ itself. Let's call it $j$:
$j = m-2^n$
Now let's use cases analysis. There are 2 cases:0

*

*$j$ is a sum of 0 or more distinct powers of 2.;

*$j$ is not a sum of 0 or more distinct powers of 2.

In the first case, by manipulation:
$m = j + 2^n$
In this case, $m$ is expressed as the sum of 2 raised to distinct powers. Since $2^n$ is the largest power of 2 in $m$ so $2^n>j$. It makes it a contradiction and, therefore, $C$ must be empty.
In the second case, $j$ is smaller than $m$. It's a contradiction since $m$ should be the smallest counterexample in $C$.
QED
