Prove that for any positive integer $n$, there exists a nonnegative integer $k$ with the property that $n$ can be written as a sum of the numbers $2^0,2^1,\dots,2^k$, each appearing once or twice.
It seems that we should begin with the canonical representation of $n$ as a sum of powers of two. To make sure that every powers of two appears, we will need to "break down" some powers of two to fill in the gaps.
On
Given any binary string $\overline{b_n\dots b_1b_0}(b_i\in \{0, 1\}, b_n = 1)$ , consider the following procedure:
Repeat 1, 2, and 3 until the string does not contain '0':
- $10\mapsto 02$: If $\overline{b_{j +1}b_j} = 10$, let $\overline{b_{j +1}b_j} \gets02$.
- Delete the highest digit if it is 0.
- $20\mapsto 12$: If $\overline{b_{j +1}b_j} = 20$, let $\overline{b_{j +1}b_j} \gets 12$.
The procedure will eventually end and give the string you want. To see why this procedure will end, note that if we define $m = \max\{i\colon b_i = 0\}$ for string $\overline{b_n\dots b_1b_0}$, then $m \leq n -1$ and decreases by at least 1 during one loop (1-2-3). As a consequence, this procedure will end in at most $n$ steps.
As an example, given '110101', this procedure gives
$110101 \mapsto 102021 \mapsto 101221 \mapsto 021221 \mapsto 21221$.
On
Consider the binary representation of $\,n+1 = 2^{k+1}+\sum_{j=0}^k b_j 2^j \;\mid\; b_j \in \{0,1\}\,$, then:
$$n = 2^{k+1}-1+\sum_{j=0}^k b_j2^j = \sum_{j=0}^k 2^{j}+\sum_{j=0}^k b_j2^j = \sum_{j=0}^k (b_j+1)2^j \quad \style{font-family:inherit}{\text{where}}\;\; b_j+1 \in \{1,2\}$$
On
The following statements are equivalent: $$n=c_02^0+c_12^1+\cdots+c_k2^k\text{ for some }c_0,c_1,\dots,c_k\in\{1,2\}$$ $$n=2^0+2^1+\cdots+2^k+m\text{ where }0\le m\le2^0+2^1+\cdots+2^k$$ $$2^0+2^1+\cdots+2^k\le n\le2(2^0+2^1+\cdots+2^k)$$ $$2^{k+1}-1\le n\le2^{k+2}-2$$ $$2^{k+1}-1\le n\lt2^{k+2}-1$$ $$2^{k+1}\le n+1\lt2^{k+2}$$ $$k+1\le\log_2(n+1)\lt k+2$$ $$k+1=\lfloor\log_2(n+1)\rfloor$$ $$k=\lfloor\log_2(n+1)\rfloor-1$$
On
If you can write all numbers from $0$ to $2^n-1$ using sums of powers of $2$ from $2^0$ to $2^{n-1}$, then you can write any number from $0$ to $2^{n+1}-1$ using sums of powers of $2$ from $2^0$ to $2^n$ by representing it as the number from $0$ to $2^n-1$ and then adding $2^n$. The property holds for $n=0$, therefore by induction it holds for all $n$.
Basically, as you say, fill in the gaps. We can always write a positive integer $n$ as a sum of powers of $2$ using the binary expansion: $$n = \delta_0 2^0 + \delta_1 2^1 + \ldots + \delta_k 2^k,$$ where $\delta_i \in \lbrace 0, 1\rbrace$. Take the least $m$ such that $\delta_i = 0$, and consider the least $l > m$ such that $\delta_l = 1$. Then, we can write: $$n = 2^0 + \ldots + 2^{m-1} + 2\cdot 2^m + 2^{m+1} + \ldots + 2^{l-1} + \delta_{l+1} 2^{l+1} + \ldots + \delta_k 2^k.$$ Note that, while this doesn't necessarily reduce the number of gaps, it does push the start of the first gap further along. You could consider using strong induction on $\lfloor\log_2(n)\rfloor - m$, where $m$ is the start of the first gap.