Page 2 of 2 FirstFirst 12
Results 16 to 24 of 24

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

  1. #16
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    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. 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...

    <br />
\frac{k}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}<br />
    <br />
\frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}<br />

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

  2. #17
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Now my only concern is this...

    <br />
\frac{k}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}<br />
    <br />
\frac{k-1}{2}=\sum_{\ell=1}^{m}2^{\jmath_\ell}<br />

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

  3. #18
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    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
    <br />
2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell}<br />
    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.
    Last edited by kingwinner; January 12th 2010 at 06:36 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    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
    <br />
2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell}<br />
    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
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    <br />
2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell}<br />

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

  6. #21
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    <br />
2^{\jmath_1}+2^{\jmath_2}+\cdots +2^{\jmath_r}=2^{k_1}+2^{k_2}+\cdots+2^{k_\ell}<br />

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

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

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

  9. #24
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by kingwinner View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

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