Strong Induction Proof: Every natural number = sum of distinct powers of 2 The question I'm looking at, is to show that every positive integer $n$ can be written as a sum of distinct powers of two. 

I can see that you can form any number based on the highest $2^t$ that is less than the number, plus some combination of $2^j&lt;n$'s. And that you can make the number odd, by adding $2^0$ at the end. 

I just don't know how to create the formula for the proof. I'm trying to figure out my base case, and then my inductive formula to figure out $k+1$, and I've got nothing.
The statement is obviously true for $n=0$.

Assume that we are given an $n\geq1$ and that it is true for all $m$ with $0\leq m&lt;n$.

When $n=2m$ then $m&lt;n$ and therefore $m=\sum_k 2^{p_k}$ with finitely many $p_k$, all of them different. It follows that $n=\sum_k 2^{p_k+1}$ with all $p_k+1$ different.

When $n=2m+1$ with an $m$ as before then $n=2^0+\sum_k 2^{p_k+1}$ with all $p_k+1$ different and different from $0$.
The subtle thing is the exact wording of the proposition.

If you want to prove:

$P(n) = $ $n$ can be expressed as a distinct sum of powers of $2$.

Initial case: $n = 1$ $P(1)$ is provable.

Induction step: $P(k) \implies P(k+1)$

then this is impossible.  $P(k) \not \implies P(k+1)$ and there is simply no way to show it does.

But if instead you try to prove.

$Q(n) = $ of all $j;  0 &lt; j &lt; 2^n$, $j $ can be written as a distinct product of powers of $2$

then $Q(k) \implies Q(k+1)$ is pretty easy to prove.

(if $0 &lt; j \le 2^{n+1}$ then either $j = m$ or $j = m + 2^n$ where $0 &lt; m &lt; 2^n$ so $m$ can be distinctly written as $\sum 2^i$.  As $m &lt; 2^n$ none of its powers of $2$ are to the $n$ power.  So  $m + 2^n = 2^n + \sum 2^i $ is a sum with distinct powers of $2$.  So $j$, whethe $j = m$ or $j = m + 2^n$ can be written as a sum of distinct powers.)

...

Another way to view this, albeit, maybe not as rigorous.  Is that induction need not be a direct $P(n) \implies P(n+1)$ progression.  And $P(n) \implies P(f(n))$ where $\cup_{i \in \mathbb N} F_i= \mathbb N$ where $F_0 = \{1\text{ or } 0\}$ and $F_{i+1} = \{f(a)|a \in \cup_{k \le i}F_i\}$, qualifies as induction as well.

Here $f(n) = n + 2^k$ where $k$ is the smallest power where $2^k &gt; n$.

(although the bit $\cup_{i \in \mathbb N} F_i= \mathbb N$ most likely will boil down to a $Q(n) \implies Q(n+1)$.  e.g.  How do we know $\{0,1\}, \{0,1, 2, 3\},\{0, 1, 2, 3,4,5,6,7\} ....$ will span $\mathbb N$?  Probably by induction.)