Sum of all powers of two 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.
 A: 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\}$$
A: 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.
A: 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$. 
A: 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$$
A: 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$.
