Strong Induction Proof: Every natural number = sum of distinct powers of 2

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

When $n=2m$ then $m<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$.

Perhaps people will find this method easier...

$Proof$. We will use strong induction to prove that $\forall n \in \mathbb{Z}^+$ we can express $n$ as a sum of distinct powers of $2$.

Base Case. For $n=1$ note that $2^0=1$ and thus for $n=1$ our proposition holds.

Inductive Hypothesis. Assume $m\in\mathbb{Z}^+$ with $1\le m \le k$ and that our proposition holds for $m$.

Inductive Step. We consider two cases.

Case 1. If $k+1$ is even then observe that $\frac{k+1}{2}$ must be an integer. Now since $1\le \frac{k+1}{2} \le k$ we know by our inductive hypothesis that $\frac{k+1}{2}$ is the sum of distinct powers of $2$. But then multiplying $\frac{k+1}{2}$ by $2$ gives

$$\frac{k+1}{2}\cdot2=k+1$$

and since (by the distributive property of multiplication over addition) each distinct power of $2$ in the sum $\frac{k+1}{2}$ is multiplied by a factor of $2$, each power of $2$ is increased by $1$ and thus remains distinct.

Case 2. If $k+1$ is odd then we know $k$ is even. Furthermore we know by our inductive hypothesis that $k$ may expressed as the sum of distinct powers of $2$. But if $k$ is even we know $k$ does not contain a $2^0=1$ in its sum of distinct powers of $2$.

Remark: To observe that $2^0=1$ does not exist in the sum of distinct powers of $2$ that makeup $k$, note that $k$, by the definition of an even integer, may be expressed as $2m$ for some $m\in\mathbb{Z}^+$ (since $k$ is positive we limit $m$ to the positive integers) and since we can view multiplication as repeated addition we have $2m = 2 + 2 + \cdots + 2 + 2$ where we are taking the sum of $m$ twos. If the sum were to contain a $2^0=1$ we clearly would need to express our integer as $2m+1$ which would make it odd not even.

Thus we see that

$$k+1=k + 2^0$$

and if $k+1$ is odd we may express $k+1$ as the sum of distinct powers of $2$.

It follows by strong mathematical induction that $\forall n \in \mathbb{Z}^+$ we can express $n$ as a sum of distinct powers of $2$. $\Box$

Finding such a representation is equivalent to expressing $n$ in binary. We can do induction as follows: Let $2^h$ be the highest power of $2$ less than or equal to $n.$ Then we must have $n-2^{h}< 2^{h+1} - 2^{h}=2^{h}(2-1)=2^{h}.$ Hence the greatest power, say $2^{g},$ of $2$ such that $2^{g}\le n-2^{h}$ must satisfy $g<h.$ By strong induction on $h$ we can assume that $n-2^{h} = \sum_{i=0}^{h-1}c_i2^i$ where each $c_i$ is either $0$ or $1.$ But then we're done, since this implies $n= \sum_{i=0}^{h-1}c_i2^i + 2^h$ is a sum of distinct powers of $2.$

To be explicit, let's include the induction hypothesis. Namely, for $h=0$ every positive $n\le 2^h=2^0=1$ can be expressed as a power of $2,$ since the only possibility is $1=2^0.$ Thus, we assume that for a given $h>0$ and any $n\le2^h,$ that such a representation exists.