# Thread: Prove that all n>0 can be defined as sums of distinct powers of 2 via induction

1. ## Prove that all n>0 can be defined as sums of distinct powers of 2 via induction

Prove by induction that every positive integer $\displaystyle n$ can be defined as a sum of distinct powers of 2, i.e. as a sum of the subset of the integers $\displaystyle 2^0, 2^1, 2^2$, and so on.
(For the inductive step, consider the case where $\displaystyle (k + 1)$ is even and the case where it is odd.)

I found a variant online on how to prove this via contradiction, but it doesn't use the odd/even cases. I'd prefer it if I had the odd/even induction case version in case it is a requirement.

2. This can be done with strong (also called course-of-value) induction, where P(k + 1) is proved not only from P(k) but from P(0), ..., P(k). (By the way, the principle of strong induction is not in fact stronger; it can be expressed using ordinary induction by changing the statement P.)

So, if k + 1 is even, represent (k + 1) / 2, which is (usually) < k, and add one to every power. If k + 1 is odd, then representation of k does not include 2^0, so add it.

3. Originally Posted by emakarov
This can be done with strong (also called course-of-value) induction, where P(k + 1) is proved not only from P(k) but from P(0), ..., P(k). (By the way, the principle of strong induction is not in fact stronger; it can be expressed using ordinary induction by changing the statement P.)

So, if k + 1 is even, represent (k + 1) / 2, which is (usually) < k, and add one to every power. If k + 1 is odd, then representation of k does not include 2^0, so add it.
That doesn't make 100% sense to me (could just be misinterpretation on my part). Do you think you could show a formulaic answer (unless that's asking too much)?

4. Let P(k) be "k can be represented as a sum of distinct powers of 2". Then P(k+1) is proved from P((k+1)/2) when k+1 is even and from P(k) when k is odd. E.g., k+1=6. Represent 3 as 1*2^0 + 1*2^1. These coefficients can be symbolically represented as a sequence (1,1,0,0,...), just for convenience. Shift the sequence to the right to get (0,1,1,0,0,0,...), or 0*2^0+1*2^1+1*2^2 = 6. By shifting the sequence of coefficients to the right, you double every term, e.g., 1*2^0 becomes 1*2^1. So the whole number also doubles and you get the representation of k+1.

5. I wonder why split it into odd and even ?!

P(1)

$\displaystyle 1=2^0$

True for n=1

P(K)

Any positive integer $\displaystyle I_k$ is a sum of powers of 2

P(K+1)

$\displaystyle I_{k+1}$ is a sum of powers of 2

Proof

$\displaystyle I_{k+1}=I_k+1=I_k+2^0$

Hence, if $\displaystyle I_k$ is a sum of powers of 2, $\displaystyle I_{k+1}$ certainly is.

The inter-term link is established among all positive integers.

True for n=1 makes it true for n=2, making it true for n=3, making it true for
all positive integers.

6. First, sorry for slow responses.

Topic title:
Prove that all n>0 can be defined as sums of distinct powers of 2 via induction
In your proposition, one would have many terms 2^0.

7. It simply serves as a basis for

$\displaystyle 2^0=1$

$\displaystyle 2^1=1+1$

$\displaystyle 2^1+2^0=1+1+1$

$\displaystyle 2^2=1+1+1+1$

$\displaystyle 2^2+2^0=1+1+1+1+1$

$\displaystyle 2^2+2^1=1+1+1+1+1+1$

$\displaystyle 2^2+2^1+2^0=1+1+1+1+1+1+1$

8. I am not sure what you mean. Basis of induction? In any case, the proof must construct a representation where all powers are different. If one constructs a representation of n according to the proof given above, one gets n = 2^0 + ... + 2^0 (n times), which is not allowed.

9. The question has the most basic of proofs,
the induction proof is very simple,
there is no need for complexity,
you have a different method.