Every natural number is sum of powers of 2

**kingwinner** · January 12th 2010, 09:45 AM

Originally Posted by Drexel28

Suppose that for all $k<n$ we have that $k$ may be represented as the sum of powers of two. If $k$ is even then $\frac{k}{2}$ satisfies the above and so $\frac{k}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}$ so that $k=\sum_{\ell=1}^{m}2^{\jmath_\ell+1}$ . If $k$ is odd then $\frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}$ so that $k=\sum_{\ell=1}^{m}2^{\jmath_\ell+1}+1=\sum_{\ell= 1}^{m}2^{\jmath_\ell+1}+2^0$ . The last step was justifiable, under the imposed conditions, since $\sum_{\ell=1}^{m}2^{\jmath_\ell+1}$ was even, hence not containing any $2^0$ .

Now my only concern is this...

$ \frac{k}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell} $
$ \frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell} $

k/2 and (k-1)/2 here must be natural numbers (or 0), but k/2 and (k-1)/2 must very possibly NOT be the same number, then why can we use the same letter "m" in the upper limit of summation?
e.g.
7=2^0 + 2^1 +2^2 (3 terms)
8=2^3 (1 term)

Will this affect the proof at all?

**Drexel28** · January 12th 2010, 11:45 AM

Originally Posted by kingwinner

Now my only concern is this...

$ \frac{k}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell} $
$ \frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell} $

k/2 and (k-1)/2 here must be natural numbers (or 0), but k/2 and (k-1)/2 must very possibly NOT be the same number, then why can we use the same letter "m" in the upper limit of summation?
e.g.
7=2^0 + 2^1 +2^2 (3 terms)
8=2^3 (1 term)

Will this affect the proof at all?

You are being overzealous now. The use of different upper indices might be more correct, but does it make a difference? It is understood that the two steps are independent and thus the m in one need not correspond with the m in the other. Proof done.

**kingwinner** · January 12th 2010, 05:52 PM

Originally Posted by Drexel28

For uniqueness, I think this works.

Suppose that $2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell}$ . We may assume WLOG that $\jmath_1\leqslant k_1$ and so dividing by $\jmath_1$ gives $1+2^{\jmath_2-\jmath_1}+\cdots=2^{k_1-\jmath_1}+2^{k_2-\jmath_1}+\cdots$ it is clear by assumption and what we imposed on $\jmath_1$ that the right side is going to be odd iff $2^{k_1-\jmath_1}=0\implies k_1=\jmath_1$ , and since it must be odd (since the left side is one plus a series of even terms) it follows that $k_1=\jmath_1$ . Thus, we may subtract from both sides $2^{k_1}$ to get $2^{\jmath_2}+\cdots=2^{k_2}+\cdots$ . Now, we may repeat this procedure of dividing by the leading term and deducing that they are only of the same parity of the leading term was the same...and dividing and repeating. Thus, by induction it follows that the two sequences must be exactly the same.

I have some questions about this proof of uniqueness.

First we get that k1=j1.
Then repeating the same steps, we can show that k2=j2.
But the problem is how can we end this? j_r and k_l are not necessarily equal (r and l are not necessarily equal).

To prove uniqueness by contradiction, we assumed at the beginning that
$ 2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell} $
To be completely general, r and l are not necessarily equal, so when we repeat your procedure of dividing by the leading term, at the end, something is going to be left over on one side of the equation but not the other. Say I assume r<l, then using your trick we can show that k1=j1, k2=j2, k_r=j_r, but we cannot say anything about j_(r+1), j_(r+2),...,j_l.

**Drexel28** · January 12th 2010, 06:41 PM

Originally Posted by kingwinner

I have some questions about this proof of uniqueness.

First we get that k1=j1.
Then repeating the same steps, we can show that k2=j2.
But the problem is how can we end this? j_r and k_l are not necessarily equal (r and l are not necessarily equal).

To prove uniqueness by contradiction, we assumed at the beginning that
$ 2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell} $
To be completely general, r and l are not necessarily equal, so when we repeat your procedure of dividing by the leading term, at the end, something is going to be left over on one side of the equation but not the other. Say I assume r<l, then using your trick we can show that k1=j1, k2=j2, k_r=j_r, but we cannot say anything about j_(r+1), j_(r+2),...,j_l.

Ok, this is starting to get annoying. Suppose you have some number $m$ and we can represent $n$ as $m=2^{\jmath_1}+\cdots 2^{\jmath_r}$ and $m=2^{k_1}+\cdots+2^{k_\ell}$ . What I showed you was how to show that these two expressions must be equal. We first assume that $\jmath_1\leqslant k_1$ WLOG since we could just reverse it otherwise. And thus we get [math1+2^{\jmath_2-\jmath_1}+\cdots=2^{k_1-\jmath_1}+\cdots[/tex], since by assumption we can see that except for the first term on each side the terms are going to be even. Thus, the left side is odd, and consequently the right side must be odd. But, how we set it up this is only going to be true if $2^{\jmath_1-k_1}=1\implies \jmath_1=k_1$ . So, we know that $\jmath_1=k_1$ and thus $2^{\jmath_1}=2^{k_1}$ . So, we may subtract them from both sides to get $2^{\jmath_2}+\cdots=2^{k_2}+\cdots$ and we follow the exact same process until we have that all the exponents must be equal

**kingwinner** · January 12th 2010, 07:13 PM

$ 2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell} $

WLOG, I assume r<l, then we can show that j1=k1, j2=k2, j3=k3, ..., j_r=k_r, and we can subtract 2^j1 from both sides, then subtract 2^j2 from both sides, then subtract 2^j3 from both sides, ..., then subtract 2^(j_r)from both sides. I understand everything up to here. What's giving me trouble is the justification AFTER this.

Then we will have some terms left over on the right hand side, namely 2^[k_(r+1)], 2^[k_(r+2)],..., 2^(k_l), and we can't use the same arguments.

**Drexel28** · January 12th 2010, 07:34 PM

Originally Posted by kingwinner

$ 2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell} $

WLOG, I assume r<l, then we can show that j1=k1, j2=k2, j3=k3, ..., j_r=k_r, and we can subtract 2^j1 from both sides, then subtract 2^j2 from both sides, then subtract 2^j3 from both sides, ..., then subtract 2^(j_r)from both sides. I understand everything up to here. What's giving me trouble is the justification AFTER this.

Then we will have some terms left over on the right hand side, namely 2^[k_(r+1)], 2^[k_(r+2)],..., 2^(k_l), and we can't use the same arguments.

They have to do this thought, if we get up to $\jmath_r$ and we subtract it and there are excess terms on the right, then we have that $0=2^{k_{r+1}}+\cdots$ which is b.s.

**kingwinner** · January 13th 2010, 10:44 PM

Originally Posted by pomp

Split your inductive step into two cases, one where k+1 is odd, and one where k+1 is even.

When k+1 is even, (k+1)/2 is a natural number and is less than k, so your inductive hypothesis holds for it. Therefore

$\frac{(k+1)}{2} = 2^{i_0} + \ldots + 2^{i_m}$

as you defined, so

$k+1 = 2^{i_0 +1} + \ldots + 2^{i_m + 1}$

I'll leave the other case to you, good luck.

hmm...I don't have a lot of experience with strong induction.
Here we split our inductive step into two cases, one where k+1 is odd, and one where k+1 is even.
So do we need to verify more than one base case (e.g. n=1 and n=2) or is one base case (n=1) totally sufficient?

**Drexel28** · January 13th 2010, 10:54 PM

Originally Posted by kingwinner

hmm...I don't have a lot of experience with strong induction.
Here we split our inductive step into two cases, one where k+1 is odd, and one where k+1 is even.
So do we need to verify more than one base case (e.g. n=1 and n=2) or is one base case (n=1) totally sufficient?

I did strong induction too? In fact, now that I look at it. Me and pomp have almost identical proofs.

If you don't mind me asking, and I really honestly don't mean this in an insulting way. Do you have some kind of attachment to this problem?

**pomp** · January 13th 2010, 10:58 PM

Originally Posted by kingwinner

hmm...I don't have a lot of experience with strong induction.
Here we split our inductive step into two cases, one where k+1 is odd, and one where k+1 is even.
So do we need to verify more than one base case (e.g. n=1 and n=2) or is one base case (n=1) totally sufficient?

No, one base case is enough.

Thread: Every natural number is sum of powers of 2

LinkBack

Thread Tools

Display

Similar Math Help Forum Discussions

For each natural number n, let An=(x in the real #s such that...

Number theory powers of numbers proof

The natural number p is prime

finding powers of a complex number

Natural log of a negative number

Search Tags