Results 1 to 7 of 7

Math Help - Strong Induction - Sum of Distinct Powers of 2

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    56

    Strong Induction - Sum of Distinct Powers of 2

    Question (21.15):

    Prove, using strong induction that every natural number can be expressed as the sum of distinct powers of 2. For example (21 = 2^4 + 2^2 + 2^0)

    I understand there is a base step, but where do I go from there?

    Thanks!
    Last edited by ccdelia7; April 25th 2008 at 06:49 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2008
    From
    United Kingdom
    Posts
    20
    Okay, I think this is how you need to be thinking:

    Induction works like dominos - you first knock down the first domino and each one knocks down the next one along and so on.

    In maths, you prove that it's true for the number 1 then you prove that IF it's true for a number, then it's true for the next number along. Then you say: "Ah, but it's true for 1, so it must be true for 2, which means it must work for 3, and 4, and 5, etc".

    So:

    "every natural number can be expressed as the sum of distinct powers of 2"
    [By the way, if this WASN'T true, then binary wouldn't really work :-) ]
    Step 1:

    Now, let's prove it for n = 1.

    1 can be written as 2^0. So that's that one done.

    Step 2:

    Let's look at a number X, which will ASSUME (we have no proof or anything, we're just going to say so) that it CAN be written as a sum of powers of 2.

    So:

    X = x_0 2^0 + x_1 2^1 + x_2 2^2 + ... + x_n 2^n

    where any of these little x_n s can be either 0 or 1. 0 indicates that there is none of this power of two in the sum. 1 indicates there is. You need distinct powers, so none of these x_n s can be more than 1.

    So to use your example,

    21 = 1 * 2^0 + 0 * 2^1 + 1 * 2^2 + 0 * 2^3 + 1 * 2^4

    Okay?

    The next number after X must be X + 1.

    X + 1 can be written as X + 2^0 so you just make sure that x_0 is turned into a 1.

    If 2^0 is "taken" (i.e. x_0 is = 1) then that means that you have to gather the existing 2^0 and the new one together and make a 2^1 which you can add (so you would add a 2^1 and take away their 2^0 because you "used it up").

    If you can't do that (if x_0 and x_1 are both = 1) then you add the 2^0 of yours to the 2^0 and the 2^1 already there to make a 2^2 ("using up the existing 2^0 and 2^1) and add that.

    The point is: Those x_0, x_1, x_2, etc in that equation that I wrote that go all the way up to x_n: You just go along them until you find the first one that's a zero and turn it into a 1 and turn all the ones before it into a zero.

    In that way, you'll have added 1 to the number and written X+1 as a sum of distinct powers of 2.

    Phew. If you recognise binary, that will sound familiar.

    Now we know that IF X can be written as a sum of powers of 2 then so can X + 1.

    Step 3:

    We know it's true for 1, because proved it in step 1. So then we know that it must be true for 1 + 1 = 2.
    But if it's true for 2 then it must be true for 2 + 1 = 3
    But if it's true for 2 then it must be true for 3 + 1 = 4
    But if it's true for 2 then it must be true for 4 + 1 = 5

    etc etc

    Congratulations, you've just proved it for all natural numbers.

    I'm not sure if that makes sense - you might need to read it a few times.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    From
    United Kingdom
    Posts
    20
    Sidenote:

    Let's count up like this, so you can see what I mean. We'll do it in the form of a table where I just write out what you times the powers of 2 by:

    NUMBER 2^0 2^1 2^2 2^3
    0 0 0 0 0
    1 1 0 0 0
    2 0 1 0 0
    3 1 1 0 0
    4 0 0 1 0
    5 1 0 1 0
    6 0 1 1 0
    7 1 1 1 0
    8 0 0 0 1

    etc


    I hope that makes it a bit clearer, but it's still probably worth thinking about.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Fedex View Post
    In maths, you prove that it's true for the number 1 then you prove that IF it's true for a number, then it's true for the next number along. Then you say: "Ah, but it's true for 1, so it must be true for 2, which means it must work for 3, and 4, and 5, etc".
    But isnt this called the weak induction?

    To prove it using strong induction, we have to assume the result holds for all numbers than n, then establish the result for 'n'.


    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2008
    From
    United Kingdom
    Posts
    20
    To prove it using strong induction, we have to assume the result holds for all numbers than n, then establish the result for 'n'.
    Damn, you're right. Think you meant "less than n" too?

    I made it needlessly more difficult than it needed to be, apparently.

    Thanks, Iso. Sorry, Ccdelia.
    Last edited by Fedex; April 25th 2008 at 08:22 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Apr 2008
    Posts
    56

    Yes!

    Yes that's awesome! - I appreciate the help!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2008
    From
    United Kingdom
    Posts
    20
    You're welcome :-)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Strong Induction.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 11th 2010, 07:19 AM
  3. How many distinct prime powers divide n ?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 10th 2010, 10:12 PM
  4. distinct powers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 24th 2010, 09:44 AM
  5. Replies: 8
    Last Post: March 4th 2010, 11:09 AM

Search Tags


/mathhelpforum @mathhelpforum