Every natural number is sum of powers of 2

**kingwinner** · January 11th 2010, 06:15 PM

[note: also under discussion in s.o.s. math board]

**pomp** · January 11th 2010, 06:22 PM

Originally Posted by kingwinner

[note: also under discussion in s.o.s. math board]

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.

**kingwinner** · January 11th 2010, 06:36 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.

So the induction hypothesis holds even when it's less than k? Are you using STRONG induction?

Also, I think the "m" may be different for each natural number n, so the labelling for the exponents for each number should be different and the number of terms may also be different for each natural number n (so we can't use the same "m" for the different natural numbers n). So can we still say $ \frac{(k+1)}{2} = 2^{i_0} + \ldots + 2^{i_m} $ ?

**Soroban** · January 11th 2010, 06:39 PM

I have an intuitive proof . . . which probably doesn't count.

Every natural number has a unique representation as a binary number.

For example: . $87 \:=\:1010111_2$

. . which represents (in reverse order): . $2^0 + 2^1 + 2^2 + 2^4 + 2^6$

**pomp** · January 11th 2010, 06:46 PM

Originally Posted by kingwinner

So the induction hypothesis holds even when it's less than k? Are you using STRONG induction?

Also, I think the "m" may be different for each natural number n, so the labelling for the exponents for each number should be different and the number of terms may also be different for each natural number n (so we can't use the same "m" for the different natural numbers n). So can we still say $ \frac{(k+1)}{2} = 2^{i_0} + \ldots + 2^{i_m} $ ?

Yes I was using strong induction, i.e the hypothesis is said to hold for all $1 \leq n \leq k$

So all natural numbers n less than k can be written in the form

$n = 2^{j_0} + \ldots + 2^{j_m}$

For some $m \geq 0$ , and some $j_0 \leq j_1 ... \leq j_m$

So if k+1 is even, (k+1)/2 < k , and so our hypothesis holds,
i.e

$(k+1)/2 = 2^{\alpha _0 } + \ldots + 2^{\alpha _ {\mu}}$

$\mu \geq 0$ , $\alpha _0 \leq \alpha _1 \leq \ldots \leq \alpha _{\mu}$

**pomp** · January 11th 2010, 06:49 PM

Originally Posted by Soroban

I have an intuitive proof . . . which probably doesn't count.

Every natural number has a unique representation as a binary number.

For example: . $87 \:=\:1010111_2$

. . which represents (in reverse order): . $2^0 + 2^1 + 2^2 + 2^4 + 2^6$

That's the first thing that came into my head too!

Isn't it the case that our inductive proof will prove the statement "Every natural number has a binary representation" and not the other way round? Or is this just semantics?

**Drexel28** · January 11th 2010, 06:56 PM

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.

**kingwinner** · January 11th 2010, 07:11 PM

Originally Posted by pomp

Yes I was using strong induction, i.e the hypothesis is said to hold for all $1 \leq n \leq k$

So all natural numbers n less than k can be written in the form

$n = 2^{j_0} + \ldots + 2^{j_m}$

For some $m \geq 0$ , and some $j_0 \leq j_1 ... \leq j_m$

So if k+1 is even, (k+1)/2 < k , and so our hypothesis holds,
i.e

$(k+1)/2 = 2^{\alpha _0 } + \ldots + 2^{\alpha _ {\mu}}$

$\mu \geq 0$ , $\alpha _0 \leq \alpha _1 \leq \ldots \leq \alpha _{\mu}$

OK, then if we're using strong induction, I am wondering how we can state the induction hypothesis properly?

For all 1≤n≤k,
$ n = 2^{j_0} + \ldots + 2^{j_m} $
where m≥0 and 0≤jo<j1<j2<...<jm

I think there is some problem stating the induction hypothesis this way, becuase for n=1, it may be m, but for n=2, it may be something else (note necessarily m), and etc...for n=k ?

**Drexel28** · January 11th 2010, 07:16 PM

Originally Posted by kingwinner

OK, then if we're using strong induction, I am wondering how we can state the induction hypothesis properly?

For all 1≤n≤k,
$ $ $n = 2^{j_0} + \ldots + 2^{j_m}
where m≥0 and 0≤jo<j1<j2<...<jm

I think there is some problem stating the induction hypothesis this way, becuase for n=1, it may be m, but for n=2, it may be something else, etc...for n=k ?

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

**kingwinner** · January 11th 2010, 07:40 PM

Thanks for explaining, but I am a bit confused as I suspect there may be some typos...

Originally Posted by Drexel28

Suppose that for all $k<n$ we have that $k$ may be represented as the sum of powers of two.

Do you mean for all 1≤n≤k-1?

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=\sum_{\ell=1} ^{m}2^{\jmath_\ell}+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$ .

I don't understand how
$ \frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell} $
can possibly imply that
$ k=\sum_{\ell=1}^{m}2^{\jmath_\ell}+1=\sum_{\ell=1} ^{m}2^{\jmath_\ell}+2^0 $
If you multiply the RHS by 2 and then add 1, shouldn't the exponent be j_l +1?

Thanks!

**Drexel28** · January 11th 2010, 07:46 PM

Originally Posted by kingwinner

Thanks for explaining, but I am a bit confused as I suspect there may be some typos...

Do you mean for all 1≤n≤k-1?

I don't understand how
$ \frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell} $
can possibly imply that
$ k=\sum_{\ell=1}^{m}2^{\jmath_\ell}+1=\sum_{\ell=1} ^{m}2^{\jmath_\ell}+2^0 $
If you multiply the RHS by 2 and then add 1, shouldn't the exponent be j_l +1?

Thanks!

It was an obvious typo. The fact that you spotted it was good, though!

**kingwinner** · January 11th 2010, 08:24 PM

So I assume the induction hypothesis is:
For all 1≤n≤k-1,
n may be represented as the sum of powers of two.

And then we proceed to show that k can be represented as the sum of powers of two.

I believe we do need to justify why k/2 ≤ k-1 and (k-1)/2 ≤ k-1 so that we can use our induction hypothesis, right?
I tried graphing these as straight lines and it's quite clear from the graph, but how can we prove it?

**Drexel28** · January 11th 2010, 08:26 PM

Originally Posted by kingwinner

So I assume the induction hypothesis is:
For all 1≤n≤k-1,
n may be represented as the sum of powers of two.

And then we proceed to show that k can be represented as the sum of powers of two.

I believe we do need to justify why k/2 ≤ k-1 and (k-1)/2 ≤ k-1 so that we can use our induction hypothesis, right?
I tried graphing these as straight lines and it's quite clear from the graph, but how can we prove it?

Now, you're just being silly.

**kingwinner** · January 11th 2010, 08:32 PM

I can see from the graph, but I can't PROVE e.g. k/2 ≤ k-1. (I was told that a graph is not a PROOF)

Suppose k is even, k≥2
k≥2 => k/2≥1, but we need the inequalty in the other way.

Alternatively, k≥2 => k-1≥1, but 1 is not always ≥ k/2, what else can I try?

**PaulRS** · January 12th 2010, 04:15 AM

Another way, note that the generating function of the number of ways a natural number can be written as a sum of distinct powers of 2 is:
$\prod_{k=0}^{\infty}{\left(1+x^{2^k}\right)}=\prod _{k=0}^{\infty}{\left(\frac{1-x^{2^{k+1}}}{1-x^{2^k}}\right)}=\tfrac{1}{1-x}=1+x+x^2+...$

Now if you want an "elementary" proof:

By induction, 0 clearly has a unique representation as sum of distinct powers of 2 -do not sum anything!-, now suppose it holds for all natural numbers up to $n-1$ .

Consider $2^{k_1}$ to be the greatest power of 2 less or equal than $n$ (1), clearly $0 \leq n-2^{k_1}\leq{n-1}$ .
So $n-2^{k_1}$ can be represented uniquely as a sum of distinct powers of 2, furthermore, none of them can be equal to $2^{k_1}$ for otherwise: $n-2^{k_1}=...+2^{k_1}$ and so $n=2^{k_1}+2^{k_1}+...=2^{k_1+1}+...>n$ by the definition (1), which is clearly a contradiction, hence $n$ can be written as a sum of distinct powers of 2.
(and that representation has to be unique since so is the representation of $n-2^{k_1}$ - note that $2^{k_1}$ is always part of the representation of $n$ since otherwise $n\leq 1+...+2^{k_1-1}=2^{k_1}-1<n$ a contradiction!, the rest follows naturally)

Thread: Every natural number is sum of powers of 2

LinkBack

Thread Tools

Display

Every natural number is sum of powers of 2

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