Positive integers expressable as sums of powers of 2

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$.

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$.

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$.