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?
Best Answer
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$.