Every natural number is sum of powers of 2

[kingwinner]

Claim: every natural number n can be uniquely expressed in the form
n = 2^jo + 2^j1 + 2^j2 +...+ 2^jm
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=2⁰ (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 = 2^jo + 2^j1 + 2^j2 +...+ 2^jm
where m≥0 and 0≤jo<j1<j2<...<jm.
With this, we need to prove that k+1=2^to + 2^t1 + 2^t2 +...+ 2^tp
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 2⁰ may not work because it is possible that jo=0, and now I feel hopeless...

Any help is much appreciated!:)

 

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

 

[kingwinner]

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.

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?

 

[ramsey2879]

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?

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?

 

[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 2⁰ to get
k+1= 2⁰ + 2^jo + 2^j1 + 2^j2 +...+ 2^jm
which is of the form
2^to + 2^t1 + 2^t2 +...+ 2^tp
with to=0, t1=jo, t2=j1, ..., t_p=j_m
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?

 

[ramsey2879]

Why do we need strong induction?

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

 

[ramsey2879]

Claim: every natural number n can be uniquely expressed in the form
n = 2^jo + 2^j1 + 2^j2 +...+ 2^jm
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=2⁰ (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 = 2^jo + 2^j1 + 2^j2 +...+ 2^jm
where m≥0 and 0≤jo<j1<j2<...<jm.
With this, we need to prove that k+1=2^to + 2^t1 + 2^t2 +...+ 2^tp
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 2⁰ may not work because it is possible that jo=0, and now I feel hopeless...

Any help is much appreciated!:)

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?

 

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

 

[kingwinner]

OK, so I will try strong induction.

Base case:(n=1)
1=2⁰ (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 = 2^jo + 2^j1 + 2^j2 +...+ 2^jm
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=2^to + 2^t1 + 2^t2 +...+ 2^tp
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 = 2^jo + 2^j1 + 2^j2 +...+ 2^jm
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.

 

[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 2⁰
=> j1=k1

Now subtract 2^j1 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!

 

[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?

 

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

 

[ramsey2879]

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:


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

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

 

[zgozvrm]

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

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.

 

[ramsey2879]

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.

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

 

[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, wouldn't 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 doesn't 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, isn't this akin to how egyptians performed multiplication, by expressing factors as sums of powers of 2?

 

[ramsey2879]

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, wouldn't 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 doesn't 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, isn't this akin to how egyptians performed multiplication, by expressing factors as sums of powers of 2?

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.

 

[crd]

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.

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

 

[ramsey2879]

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

Thanks for the link It does show that the Egyptian knew to write a number as a sum of unique powers of 2 although the did not include zeros for the missing powers as you do when using base 2 notation.