8
$\begingroup$

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

  • 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?2012-07-30
  • 0
    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.2012-07-30
  • 0
    @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."?2012-07-30
  • 0
    @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.2012-07-30
  • 0
    If P(k) is even then the answer should be obvious. If P(k) is odd, then $m = \dfrac{P(k)+1}{2}$ can be expressed as the sum of powers of $2$ and P(k+1) = 2m + 1.2016-03-21
  • 0
    The trick is that you aren't doing the usual induction on P(n) => P(n+1) but on P(k; k < 2^n) => P(2^n + k).2017-01-13
  • 0
    Don't do induction on $n$. Do induction on $t$. the proposition isn't P(n) = "n can be written as a sum". It's P(t) = "Every n < 2^t can be written as a sum".2017-01-13

4 Answers 4