# Every natural number is sum of powers of 2

1. Jan 11, 2010

### kingwinner

Claim: every natural number n can be uniquely expressed in the form
n = 2jo + 2j1 + 2j2 +...+ 2jm
where m≥0 and 0≤jo<j1<j2<...<jm.

===========================

So I think we need to prove two things: (i) existence and (ii) uniqueness.
My idea is to prove existence first by mathematical induction, and after that prove uniqueness.
Base case:(n=1)
1=20 (jo=0, m=0)
So the claim is true for n=1

Induction hypothesis: Assume the claim is true for n=k, k≥1
i.e. k = 2jo + 2j1 + 2j2 +...+ 2jm
where m≥0 and 0≤jo<j1<j2<...<jm.
With this, we need to prove that k+1=2to + 2t1 + 2t2 +...+ 2tp
where p≥0 and 0≤to<t1<t2<...<tp. (where p is not necessarily equal to m)
And now I am stuck. How can I prove that n=k+1 is true using the induction hypothesis? Notice that adding 20 may not work because it is possible that jo=0, and now I feel hopeless...

Any help is much appreciated!:)

2. Jan 11, 2010

### JSuarez

This is the base 2 representation. To apply induction to the general case, divide n by 2, obtaining n = 2q + r, with r = 0 or 1, and apply the induction hypothesis to q.

3. Jan 11, 2010

### kingwinner

Sorry, I don't get it...

In my first post, am I right so far? (i.e. are my base case and induction hypothesis correct?) Or are you suggesting something else?

4. Jan 11, 2010

### ramsey2879

Looks like a modified form of induction. Assume the hypothesis works for ALL n from 1 to m then prove that it is true for n = m + 1. Would that be what JSuarez is suggesting? Would it be a correct form of induction?

5. Jan 11, 2010

### kingwinner

Why do we need strong induction?

Continuing from my work in post 1, may I should divide into 2 cases?
Case 1: jo>0
Case 2: jo=0

For Case 1: jo>0
Using the induction hypothesis, I can simply add 20 to get
k+1= 20 + 2jo + 2j1 + 2j2 +...+ 2jm
which is of the form
2to + 2t1 + 2t2 +...+ 2tp
with to=0, t1=jo, t2=j1, ..., tp=jm
so p≥0 and 0≤to<t1<t2<...<tp are satisfied, and we're done with case 1.

But I have no clue how to do the proof for case 2...can somebody help, please?

6. Jan 12, 2010

### ramsey2879

Because it is an eazy proof when you use jSuarez's idea to divide m+1 by 2.

7. Jan 12, 2010

### ramsey2879

How about every 2 occurences of 2 to the same power can be replaced with 2 to the next power again and again until there is at most one 2 of any given power?

8. Jan 12, 2010

### JSuarez

What I suggested is Strong Induction, but you may also see it as a form of iterative division (by 2); given a number $$n$$, we have:

$$n=2q_0+r_0$$
$$q_0=2q_1+r_1$$

therefore $$n = 2\left(2q_1+r_1\right) + r_0 = 2^{2}q_1 + 2r_1 + r_0$$

Eventually the process stops when $$q_m<2$$; as the sequence of remainders $$r_i \in \left\{0,1\right\}$$, you have the required representation.

9. Jan 12, 2010

### kingwinner

OK, so I will try strong induction.

Base case:(n=1)
1=20 (jo=0, m=0)
So the claim is true for n=1

Induction hypothesis: Assume the claim is true for 1≤n≤k, k≥1
So for example, for n=k, assume k = 2jo + 2j1 + 2j2 +...+ 2jm
where m≥0 and 0≤jo<j1<j2<...<jm.
(but I am not sure how to write in terms of notation for the other natural numbers 1,2,...,k-1)
With this, we need to prove that k+1=2to + 2t1 + 2t2 +...+ 2tp
where p≥0 and 0≤to<t1<t2<...<tp. (where p is not necessarily equal to m)

Now if I divide into two cases (case 1: k is odd, case 2: k is even), will that work?
If k is odd, k+1 is even, and (k+1)/2 is an integer, and by induction hypothesis it can be expressed as sums of powers of 2. Is that right?

But in strong induction, how can I state the induction hypothesis properly?
For n=k, we can say k = 2jo + 2j1 + 2j2 +...+ 2jm
where m≥0 and 0≤jo<j1<j2<...<jm.
But how about n=1,2,...,k-1? The exponents for each natural number is not necessarily the same, and "m" is not necessarily the same.

Last edited: Jan 13, 2010
10. Jan 13, 2010

### kingwinner

To prove uniqueness, suppose
[itex]
2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell}
[/tex]

WLOG, I assume j1≤k1.
Divide both sides by j1, we get:
[itex]
1+2^{\jmath_2-\jmath_1}+\cdots=2^{k_1-\jmath_1}+2^{k_2-\jmath_1}+\cdots
[/tex]
The left side is odd, so the right side must be odd and this implies that the first term of the RHS must be 20
=> j1=k1

Now subtract 2j1 from both sides
=> [itex]
2^{\jmath_2}+\cdots=2^{k_2}+\cdots
[/tex]

Repeat the above steps, we can show that j2=k2, j3=k3,...

But now how can I justify properly that ALL of the j's are equal to the corresponding k's? To prove rigorously, do I need induction? But I don't think induction works becuase rather than the set of all natural numbers, here there is an "upper bound" on the subscript of the j's and k's.

Any help is much appreciated!

11. Jan 13, 2010

### kingwinner

My point is mathematical induction are used to prove statements that are true for all natural numbers, or the starting point may be higher, e.g. for all n=4,5,6,... Both are INFINITE sets.

How can we use mathematical induction to prove that something is true for e.g. n=1,2,3,4? (instead of continuing forever, here there is a cut off point at n=4). How can we use math induction to prove statements like this?

12. Jan 14, 2010

### JSuarez

Apologies for the late response, but the last days were hectic.

Look, you're complicating things too much; the result you want to prove is just the existence and uniqueness of the binary representation of a natural number and, for any base > 1, this is actually simple.

But there is also some confusions about induction in $$\mathbb N$$ that I'll try to dispel.

(1) The basic (or weak) form of induction is this: for any set $$X \subseteq \mathbb N$$, if:

$$0\in X$$ and $$\forall n \in \mathbbN\left(n \in X\rightarrow n + 1 \in X\right)$$

then we may conclude that $$\forall n \in \mathbb N \left(n\in X\right)$$.

(2) And there is an alternative form of induction (the equivalence between the two is proved in mathematical logic), called strong (or course-of-values), induction; it states that, for any set $$X \subseteq \mathbb N$$, if:

$$\forall n,m \in \mathbb N \left(m<n \wedge m \in X \rightarrow n \in X \right)$$

then we may conclude $$\forall n \in \mathbb N \left(n\in X\right)$$.

The principal difference between the weak and strong induction schemes is that the latter assumes that the hypothesis is valid for all the natural numbers less than n, while the former only assumes truth for the immediate predecessor of n. One consequence of the stronger assumption is that there is no base cases in strong induction; they are always automatically true.

Now, I'll repeat the original argument:

Let $$n\in \mathbb N$$; dividing by 2, we have:

$$n=2q+r , 0\leq r \leq 1$$

Now, q < n; so, applying strong induction (so that q doesn't need to be the immediate predecessor of n), we may assume that:

$$q = 2^{i_1}+2^{i_2}+...+2^{i_k}$$

And introducing this in n = 2q + r, we have:

$$n = 2\left(2^{i_1}+2^{i_2}+...+2^{i_k}\right) + r= 2^{i_1+1}+2^{i_2+1}+...+2^{i_k+1}+r$$

If r = 0, we're done; if r =1, then replace by $$2^{0}$$.

13. Jan 17, 2010

### ramsey2879

If I hear you right I think you don't have a proof in strong induction if there is no base case for which the hypothesis is true!

I. E. Proof that there are more than one unique form of

$$n = 2\left(2^{i_1}+2^{i_2}+...+2^{i_k}\right) + r= 2^{i_1+1}+2^{i_2+1}+...+2^{i_k+1}+r$$

Proof by strong induction,

Let $$n\in \mathbb N$$; dividing by 2, we have:

$$n=2q+r , 0\leq r \leq 1$$

Now, q < n; so, applying strong induction (so that q doesn't need to be the immediate predecessor of n), we may assume that:

$$q = 2^{i_1}+2^{i_2}+...+2^{i_k}$$ and
$$q = 2^{j_1}+2^{j_2}+...+2^{j_m}$$
And introducing this in n = 2q + r, we have:
$$n = 2*(2^{i_1}+2^{i_2}+...+2^{i_k}) +r$$ and
$$n = 2*( 2^{j_1}+2^{j_2}+...+2^{j_m}) + r$$
If r = 0, we're done; if r =1, then replace by $$2^{0}$$

14. Jan 23, 2010

### zgozvrm

You're wanting to prove is that any natural base 10 number can be converted to binary? So what? They can also be converted to base 3, base 4, or any other base. And, in each case there is only one (unique) way in which the number can be written.

15. Jan 24, 2010

### ramsey2879

Yes and one proof would be very much the same as here. Do you have a better proof?

16. Feb 15, 2010

### crd

Maybe I am missing something, but if we have shown that 1 is a power of 2, and for some natural number k=>1, we are assuming k is a sum of powers of 2, wouldnt k+1 necessarily be of the correct form since we are adding a power of two to a finite sum of powers of two we are left with a finite sum of powers of 2.

Maybe said another way, since 1 is a power of 2,
k=1+1+...+1 for any k is a sum of powers of 2

of course this doesnt quite fit your hypothesis since you want exponents to be unique, but one could easily group terms to express k in the desired form.

Its not as elegant as the other solution but it seems as though this works(I say that somewhat hesitantly)

Btw, isnt this akin to how egyptians performed multiplication, by expressing factors as sums of powers of 2?

17. Feb 15, 2010

### ramsey2879

Your right, but it would be a great deal of more work to "group terms" to make the exponents of 2 different from each other when there is a simple algorithm to express any natural number as the sum of unique powers of 2. I am quite sure that the early Egyptians were aware of this if they did their multiplication in base 2, but I never heard of that before. BTW it is much simpler to do multiplication in base 2 if the numbers are properly in their unique base 2 format.

Last edited: Feb 15, 2010
18. Feb 15, 2010

### crd

http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication

19. Feb 16, 2010