http://sites.google.com/site/asdfasdf23135/nt1.JPG

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

Printable View

- Jan 11th 2010, 06:15 PMkingwinnerEvery natural number is sum of powers of 2
http://sites.google.com/site/asdfasdf23135/nt1.JPG

[note: also under discussion in s.o.s. math board] - Jan 11th 2010, 06:22 PMpomp
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. - Jan 11th 2010, 06:36 PMkingwinner
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}

$? - Jan 11th 2010, 06:39 PMSoroban

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 $

- Jan 11th 2010, 06:46 PMpomp
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}$ - Jan 11th 2010, 06:49 PMpomp
- Jan 11th 2010, 06:56 PMDrexel28
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. - Jan 11th 2010, 07:11 PMkingwinner
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 ? - Jan 11th 2010, 07:16 PMDrexel28
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$.

- Jan 11th 2010, 07:40 PMkingwinner
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?

Quote:

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

$\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! - Jan 11th 2010, 07:46 PMDrexel28
- Jan 11th 2010, 08:24 PMkingwinner
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? - Jan 11th 2010, 08:26 PMDrexel28
- Jan 11th 2010, 08:32 PMkingwinner
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? - Jan 12th 2010, 04:15 AMPaulRS
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)