Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question
2  
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? – Tim Duff 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

1 Answer

up vote 4 down vote

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.