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

-
You'll need to separately consider the cases where $k+1$ is odd and even. The former is trivial. You really only use induction for the latter. What can you say about $\frac{k+1}{2}$ in this case? –  user17794 Jul 30 '12 at 0:24
It seems to me that what you want to prove is that, for each integer $m$, that all the integers from $2^m$ to $2^{m+1}-1$ can be written as the sum of distinct power of 2. This can be readily (he says without proof) proved by induction. –  marty cohen Jul 30 '12 at 0:40
@RickDecker, I'm a bit confused here. Does your edit contain an extra statement: "And that you can make the number odd, by adding $2^0$ at the end."? –  user2468 Jul 30 '12 at 1:22
@J.D. Okay, now I'm doubly confused. Let me try once more. (My initial comment, a few hours ago, was): The sentence in question was part of the original post, despite the fact that it appears nowhere in the edit history. (My current comment is) My initial comment has vanished. I'm leaving this thread forever; it's making me doubt my sanity and at my age that's a very bad thing. –  Rick Decker Jul 30 '12 at 18:42

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.

-
We know how to express each and every positive integer(n) in any positive integer base(b). In that case $n=\sum_{0≤r} a_rb^r\ where\ 0≤a_r<b$. If b=2, $n=\sum_{0≤r} a_r2^r\ where\ 0≤a_r<2 =>here\ a_r=0,1$. Clearly, every positive integer is the sum of distinct powers of 2. Why induction is at all required? –  lab bhattacharjee Jul 30 '12 at 5:53
@labbhattacharjee I merely tried to give a proof of this fact, as it seemed to be the OP's goal to prove it using induction. I'm not sure whether there can be a proof without induction. –  Andrew Jul 30 '12 at 14:17

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

-