Results 1 to 9 of 9

Math Help - Prove that all n>0 can be defined as sums of distinct powers of 2 via induction

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    232

    Prove that all n>0 can be defined as sums of distinct powers of 2 via induction

    Prove by induction that every positive integer n can be defined as a sum of distinct powers of 2, i.e. as a sum of the subset of the integers 2^0, 2^1, 2^2, and so on.
    (For the inductive step, consider the case where (k + 1) is even and the case where it is odd.)

    I found a variant online on how to prove this via contradiction, but it doesn't use the odd/even cases. I'd prefer it if I had the odd/even induction case version in case it is a requirement.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    This can be done with strong (also called course-of-value) induction, where P(k + 1) is proved not only from P(k) but from P(0), ..., P(k). (By the way, the principle of strong induction is not in fact stronger; it can be expressed using ordinary induction by changing the statement P.)

    So, if k + 1 is even, represent (k + 1) / 2, which is (usually) < k, and add one to every power. If k + 1 is odd, then representation of k does not include 2^0, so add it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2010
    Posts
    232
    Quote Originally Posted by emakarov View Post
    This can be done with strong (also called course-of-value) induction, where P(k + 1) is proved not only from P(k) but from P(0), ..., P(k). (By the way, the principle of strong induction is not in fact stronger; it can be expressed using ordinary induction by changing the statement P.)

    So, if k + 1 is even, represent (k + 1) / 2, which is (usually) < k, and add one to every power. If k + 1 is odd, then representation of k does not include 2^0, so add it.
    That doesn't make 100% sense to me (could just be misinterpretation on my part). Do you think you could show a formulaic answer (unless that's asking too much)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Let P(k) be "k can be represented as a sum of distinct powers of 2". Then P(k+1) is proved from P((k+1)/2) when k+1 is even and from P(k) when k is odd. E.g., k+1=6. Represent 3 as 1*2^0 + 1*2^1. These coefficients can be symbolically represented as a sequence (1,1,0,0,...), just for convenience. Shift the sequence to the right to get (0,1,1,0,0,0,...), or 0*2^0+1*2^1+1*2^2 = 6. By shifting the sequence of coefficients to the right, you double every term, e.g., 1*2^0 becomes 1*2^1. So the whole number also doubles and you get the representation of k+1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    I wonder why split it into odd and even ?!

    P(1)

    1=2^0

    True for n=1

    P(K)

    Any positive integer I_k is a sum of powers of 2

    P(K+1)

    I_{k+1} is a sum of powers of 2

    Proof

    I_{k+1}=I_k+1=I_k+2^0

    Hence, if I_k is a sum of powers of 2, I_{k+1} certainly is.

    The inter-term link is established among all positive integers.

    True for n=1 makes it true for n=2, making it true for n=3, making it true for
    all positive integers.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    First, sorry for slow responses.

    Topic title:
    Prove that all n>0 can be defined as sums of distinct powers of 2 via induction
    In your proposition, one would have many terms 2^0.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    It simply serves as a basis for


    2^0=1

    2^1=1+1

    2^1+2^0=1+1+1

    2^2=1+1+1+1

    2^2+2^0=1+1+1+1+1

    2^2+2^1=1+1+1+1+1+1

    2^2+2^1+2^0=1+1+1+1+1+1+1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    I am not sure what you mean. Basis of induction? In any case, the proof must construct a representation where all powers are different. If one constructs a representation of n according to the proof given above, one gets n = 2^0 + ... + 2^0 (n times), which is not allowed.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    The question has the most basic of proofs,
    the induction proof is very simple,
    there is no need for complexity,
    you have a different method.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sums of powers in integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 1st 2011, 08:02 PM
  2. How many distinct prime powers divide n ?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 10th 2010, 10:12 PM
  3. distinct powers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 24th 2010, 09:44 AM
  4. Induction proof involving sums of consecutive powers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2009, 06:01 AM
  5. Replies: 6
    Last Post: April 25th 2008, 08:23 AM

Search Tags


/mathhelpforum @mathhelpforum