Page 1 of 2 12 LastLast
Results 1 to 15 of 24

Math Help - Every natural number is sum of powers of 2

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Every natural number is sum of powers of 2




    [note: also under discussion in s.o.s. math board]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by kingwinner View Post



    [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.
    Last edited by pomp; January 11th 2010 at 06:23 PM. Reason: typos
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by pomp View Post
    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 <br />
\frac{(k+1)}{2} = 2^{i_0} + \ldots + 2^{i_m}<br />
?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,548
    Thanks
    541

    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

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by kingwinner View Post
    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 <br />
\frac{(k+1)}{2} = 2^{i_0} + \ldots + 2^{i_m}<br />
?
    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}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by Soroban View Post

    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    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.
    Last edited by Drexel28; January 11th 2010 at 07:41 PM. Reason: Clarity
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by pomp View Post
    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,
    <br />
n = 2^{j_0} + \ldots + 2^{j_m}<br />
    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 ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    OK, then if we're using strong induction, I am wondering how we can state the induction hypothesis properly?

    For all 1≤n≤k,
    <br />
    " alt="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.
    Last edited by Drexel28; January 11th 2010 at 07:47 PM. Reason: Clarity
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Thanks for explaining, but I am a bit confused as I suspect there may be some typos...

    Quote Originally Posted by Drexel28 View Post
    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
    <br />
\frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}<br />
    can possibly imply that
    <br />
k=\sum_{\ell=1}^{m}2^{\jmath_\ell}+1=\sum_{\ell=1}  ^{m}2^{\jmath_\ell}+2^0<br />
    If you multiply the RHS by 2 and then add 1, shouldn't the exponent be j_l +1?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    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
    <br />
\frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}<br />
    can possibly imply that
    <br />
k=\sum_{\ell=1}^{m}2^{\jmath_\ell}+1=\sum_{\ell=1}  ^{m}2^{\jmath_\ell}+2^0<br />
    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!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    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?
    Last edited by kingwinner; January 12th 2010 at 12:48 AM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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)
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 14th 2011, 02:46 AM
  2. Number theory powers of numbers proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 31st 2010, 08:55 PM
  3. The natural number p is prime
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 11th 2009, 08:16 AM
  4. finding powers of a complex number
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: December 10th 2008, 07:35 PM
  5. Natural log of a negative number
    Posted in the Calculus Forum
    Replies: 7
    Last Post: December 19th 2007, 02:05 PM

Search Tags


/mathhelpforum @mathhelpforum