• Lucid Dreaming - Dream Views




    Results 1 to 4 of 4
    Like Tree2Likes
    • 2 Post By Xei

    Thread: Help: I passed Calc 1-3 with flying colors, now I'm utterly failing discrete math.

    1. #1
      Member Hercuflea's Avatar
      Join Date
      May 2008
      Gender
      Posts
      868
      Likes
      7
      DJ Entries
      2

      Help: I passed Calc 1-3 with flying colors, now I'm utterly failing discrete math.

      So I just can't get the hang of discrete math. Here is a proof I have been working on, but haven't gotten far with.

      1. The problem statement, all variables and given/known data

      "Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 2^0 = 1, 2^1 = 2, 2^2= 4, and so on. [Hint: for the inductive step, separately consider the case where k+1 is even and where it is odd. When it is even, note that (k+1)/2 is an integer.]

      2. Relevant equations

      For strong induction, Assume P(1) and P(2) and P(3) and...and P(k) and show that these all ---> P(k+1)

      3. The attempt at a solution

      P(n): every integer n≥1 can be written as a sum of distinct powers of 2.

      Basis step: clearly P(1) = 1 = 2^0
      1 = 1

      Inductive Step: Assume for some k∈N that k can be written as distinct powers of 2. Show that k+1 can be written as distinct powers of 2.


      Case 1: k is even

      So k = 2^a + 2^b + 2^c + ....

      a, b, c, ...≥0

      Then k + 1 = k + 2^0
      k + 1 = k + 1

      Case 2: k is odd

      So k = 2^0 + 2^a + 2^b + 2^c +...

      Where a, b, c, ...≥0

      So k+1 = 2^0 + 2^0 + 2^a + 2^b + 2^c

      k + 1 = 2^0(1+1) + 2^a + 2^b + 2^c

      k+1 = k + 2????

      How do I set this equation up properly? I can't seem to find a relationship that works out.
      Last edited by Hercuflea; 06-30-2012 at 02:12 AM. Reason: Missed a Carrot!
      "La bellezza del paessa di Galilei!"

    2. #2
      Member
      Join Date
      Apr 2012
      LD Count
      12
      Gender
      Location
      My house..
      Posts
      66
      Likes
      15
      I would help if I could but I can only stare blankly and only slightly understand about 2% of what I just read

    3. #3
      Member Hercuflea's Avatar
      Join Date
      May 2008
      Gender
      Posts
      868
      Likes
      7
      DJ Entries
      2
      Well the stuff at the bottom is probably wrong but it's what I have done so far.
      "La bellezza del paessa di Galilei!"

    4. #4
      Xei
      UnitedKingdom Xei is offline
      Banned
      Join Date
      Aug 2005
      Posts
      9,984
      Likes
      3082
      Your problem is a misunderstanding of induction. Don't worry about this, it's very new when you first meet it.

      Firstly, your proposition doesn't have the right form. The kind of statements you try to prove by induction are statements which are somehow statements about all positive integers (or in fact any countably infinite set). Here the statement is 'all positive integers are sums of distinct powers of 2'. This can be rephrased as, '1 is a sum of distinct powers of 2, and 2 is a sum of distinct powers of 2, and 3 is a sum of distinct powers of 2, ...' and so on. These individual statements, about single numbers, are what we represent by P(1), P(2), P(3), ... . As it stands your proposition, 'P(n): every integer n≥1 can be written as a sum of distinct powers of 2', doesn't make much sense. n is supposed to be some fixed number, and P(n) represents the statement for that number; if we took n to be 5 for instance, your proposition P(5) would be 'every integer 5 ≥ 1 can be written as a sum of distinct powers of 2'. What we want is, 'P(n): n is a sum of distinct powers of 2'.

      Secondly, there's a difference between strong induction and weak induction (technically you can use weak induction to prove anything that you can prove by strong induction, but that's not important here and in any case it's less messy to use strong induction). You are trying to use weak induction, where you assume that P(k-1) is true in order to prove P(k), and thus P is true for all positive integers n (given P(1)), by weak induction. Hopefully it's obvious how this works; it's always valid to assume that the previous statement is true, because you can reach it by 'building up' from 1.

      Strong induction is different: again, you wish to prove P(k), but this time you can assume that all statements P(1), P(2), ... , P(k-1) are true. This is more powerful; maybe you need to know P(3) in order to prove P(5), for instance. You couldn't do it simply with weak induction. Hopefully it's again clear why this means that P(n) is true for all positive integers n; once again you 'build up' from 1, but this time you remember all of the things you have proven so far, instead of just the previous one.

      Maybe you can take another shot now. Your proof for when k is odd is correct; k - 1 is even but with no odd term, so k is the same sum of distinct powers of 2 but with 1 added on. You can do this bit by weak induction. But when k is even, instead of looking at k - 1, you'll want to look at k/2, as the question suggests. Here you will be using strong induction.
      PhilosopherStoned and fOrceez like this.

    Similar Threads

    1. I cant get passed SP. Any Pointers?
      By wearetheenemy in forum Wake Initiated Lucid Dreams (WILD)
      Replies: 3
      Last Post: 01-28-2012, 07:27 AM
    2. Talking to some one who's passed?
      By theunseen in forum Beyond Dreaming
      Replies: 6
      Last Post: 11-10-2007, 03:18 PM
    3. A Great Math Program (Math Mecanix)
      By TripleX223 in forum General Dream Discussion
      Replies: 2
      Last Post: 11-06-2007, 12:19 PM
    4. Replies: 8
      Last Post: 08-29-2007, 04:05 AM
    5. Replies: 8
      Last Post: 08-29-2007, 04:05 AM

    Bookmarks

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •