# Thread: Every natural number is sum of powers of 2

1. ## Every natural number is sum of powers of 2

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

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

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

as you defined, so

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

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

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

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

as you defined, so

$\displaystyle 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 $\displaystyle \frac{(k+1)}{2} = 2^{i_0} + \ldots + 2^{i_m}$?

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

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

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

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

5. 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 $\displaystyle \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 $\displaystyle 1 \leq n \leq k$

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

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

For some $\displaystyle m \geq 0$ , and some $\displaystyle 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

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

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

6. 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: .$\displaystyle 87 \:=\:1010111_2$

. . which represents (in reverse order): .$\displaystyle 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?

7. For uniqueness, I think this works.

Suppose that $\displaystyle 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 $\displaystyle \jmath_1\leqslant k_1$ and so dividing by $\displaystyle \jmath_1$ gives $\displaystyle 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 $\displaystyle \jmath_1$ that the right side is going to be odd iff $\displaystyle 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 $\displaystyle k_1=\jmath_1$. Thus, we may subtract from both sides $\displaystyle 2^{k_1}$ to get $\displaystyle 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.

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

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

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

For some $\displaystyle m \geq 0$ , and some $\displaystyle 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

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

$\displaystyle \mu \geq 0$ , $\displaystyle \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,
$\displaystyle 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 ?

9. 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,
$\displaystyle$
$\displaystyle 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 $\displaystyle k<n$ we have that $\displaystyle k$ may be represented as the sum of powers of two. If $\displaystyle k$ is even then $\displaystyle \frac{k}{2}$ satisfies the above and so $\displaystyle \frac{k}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}$ so that $\displaystyle k=\sum_{\ell=1}^{m}2^{\jmath_\ell+1}$. If $\displaystyle k$ is odd then $\displaystyle \frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}$ so that $\displaystyle 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 $\displaystyle \sum_{\ell=1}^{m}2^{\jmath_\ell+1}$ was even, hence not containing any $\displaystyle 2^0$.

10. 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 $\displaystyle k<n$ we have that $\displaystyle k$ may be represented as the sum of powers of two.
Do you mean for all 1≤n≤k-1?

If $\displaystyle k$ is even then $\displaystyle \frac{k}{2}$ satisfies the above and so $\displaystyle \frac{k}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}$ so that $\displaystyle k=\sum_{\ell=1}^{m}2^{\jmath_\ell+1}$. If $\displaystyle k$ is odd then $\displaystyle \frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}$ so that $\displaystyle 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 $\displaystyle \sum_{\ell=1}^{m}2^{\jmath_\ell+1}$ was even, hence not containing any $\displaystyle 2^0$.
I don't understand how
$\displaystyle \frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}$
can possibly imply that
$\displaystyle 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!

11. 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
$\displaystyle \frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}$
can possibly imply that
$\displaystyle 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!

12. 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?

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

14. 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?

15. 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:
$\displaystyle \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 $\displaystyle n-1$.

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

Page 1 of 2 12 Last