Results 1 to 9 of 9

Math Help - Dealing with Binary Sequences Using PMI2 & Simple Set Theory

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    8

    Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Hello, second post here! I am starting to really enjoy Discrete, but I am still getting snagged on a few thought processes. Hopefully the more I do, the easier it gets!

    A little assistance would be very grateful!

    Question: For each positive integer n, let S(n) denote the set of all binary sequences of length n. For example, S(2) = { (0, 0), (0, 1), (1, 0), (1, 1) } (for each positive integer n, S(n) contains 2^n elements). Use mathematical induction to prove that for every positive integer n, there are exactly 2^(n−1) elements of S(n) that contain an even number of entries equal to 1. For example, in S(2), the elements with an even number of entries equal to 1 are (0, 0) and (1, 1) (the first sequence has 0 entries equal to 1, and 0 is even, while the second sequence has 2 entries equal to 1). Thus S(2) has 2 = 2^(2−1) sequences with an even number of entries equal to 1.

    Answer: Let P(n) denote the predicate "Every set of binary sequences of length n has exactly 2^(n-1) elements which have an even number of entries equal to 1".

    We set n* >= 1, as n* < 1 would result in, say in the example of n* = 0, 2^(0-1) < 1.

    We try PMI2
    need to prove
    (1) P(1) is True.
    (2) For all n, n >= 1 [ P(1), P(2), P(3), ... P(n)] -> P(n+1)

    (1) P(1): S(1) = {(0), (1)}. In S(1), we see that there is contained one case of an even numbered entry, that of (0), which is in sync with 2^(n-1) -> 2^(1-1) = 2^0 = 1. Thus, by inspection, P(1) is True.

    (2) To prove (2), let n >= 1 be such that [ P(1), P(2), P(3), ... P(n)] are all true.

    _____

    This is as far as I've been able to reach. First I'd like to apologize for my lack of knowledge around the math wrap system, as I am sure many of things that I did not properly format have better looking alternatives.

    Secondly, I just want to express my "hunches" on the possible answer, just so you can hone in onto my thought process and give suggestions to improve my mathematical outlook. I am thinking that it might have to do with how P(n+1) allows S(n+1) to produce 2^n results, as 2^((n+1) - 1) = 2^n.

    Also, as in almost all beginner mathematical questions, I'm sure that there are multiple ways of completing this question, but I would like to stress that I would be grateful if any assistance I receive stick roughly to the format I've presented, as it's what I know.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Quote Originally Posted by demelode View Post
    Question: [B]For each positive integer n, let S(n) denote the set of all binary sequences of length n. Use mathematical induction to prove that for every positive integer n, there are exactly 2^(n−1) elements of S(n) that contain an even number of entries equal to 1.
    Answer: Let P(n) denote the predicate "Every set of binary sequences of length n has exactly 2^(n-1) elements which have an even number of entries equal to 1".
    We set n* >= 1, as n* < 1 would result in, say in the example of n* = 0, 2^(0-1) < 1.
    Here is the idea. Every string is S(n+1) is formed by taking a string from S(n) and adding a 0 to get a new one in S(n+1) and adding 1 to another.
    If you note 2^n+2^n=2(2^n)=2^{n+1}.
    There are 2^{n-1} strings in S(n) with an odd number of 1's. If we add a 1 to each of those we get a string in S(n+1) with an even number of 1's.
    So how many new strings are there?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    8

    Re: Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Quote Originally Posted by Plato View Post
    Here is the idea. Every string is S(n+1) is formed by taking a string from S(n) and adding a 0 to get a new one in S(n+1) and adding 1 to another.
    If you note 2^n+2^n=2(2^n)=2^{n+1}.
    There are 2^{n-1} strings in S(n) with an odd number of 1's. If we add a 1 to each of those we get a string in S(n+1) with an even number of 1's.
    So how many new strings are there?
    There would be 2^(n-1) of these new strings as all the odd from the previous are now even! Thank you for the assistance! I've always had trouble conceptualizing questions, but the way you've presented this too me really helps me visualize what's going on.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Quote Originally Posted by demelode View Post
    There would be 2^(n-1) of these new strings as all the odd from the previous are now even! Thank you for the assistance! I've always had trouble conceptualizing questions, but the way you've presented this too me really helps me visualize what's going on.
    Also do not forget that by a 0 to a string with an even number of 1's in S(n) also give a string in S(n+1) with an even number of 1's.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2011
    Posts
    8

    Re: Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Quote Originally Posted by Plato View Post
    Also do not forget that by a 0 to a string with an even number of 1's in S(n) also give a string in S(n+1) with an even number of 1's.
    But wouldn't it also be the case that:

    adding a 1 to an even = odd
    adding a 0 to an even = even
    adding a 1 to an odd = even
    adding a 0 to an odd = odd

    Would this not just balance out? So is it still indeed 2^(n-1), or are you suggesting my answer to your proposition was incorrect?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Quote Originally Posted by demelode View Post
    But wouldn't it also be the case that:

    adding a 1 to an even = odd
    adding a 0 to an even = even
    adding a 1 to an odd = even
    adding a 0 to an odd = odd

    Would this not just balance out? So is it still indeed 2^(n-1), or are you suggesting my answer to your proposition was incorrect?
    By adding a 1 to all the odds in S(n) we get 2^{n-1} evens in S(n+1).

    By adding a 0 to all the evens in S(n) we get 2^{n-1} evens in S(n+1).

    Now 2^{n-1}+2^{n-1}=2^{n} evens in S(n+1)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2011
    Posts
    8

    Re: Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Quote Originally Posted by Plato View Post
    By adding a 1 to all the odds in S(n) we get 2^{n-1} evens in S(n+1).

    By adding a 0 to all the evens in S(n) we get 2^{n-1} evens in S(n+1).

    Now 2^{n-1}+2^{n-1}=2^{n} evens in S(n+1)
    Bah I wrote out a whole thing and hit Go Advanced by accident. Let's try this again...

    I am following what your saying here. The total size of S(n+1) was proven to be 2^(n+1), and now the amount of evens to be 2^n. My confusion is - how does this attach to the goal of proving P(n+1) is true? Shouldn't the amount of evens be 2^(n-1) for it to be true, or am I missing something?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Quote Originally Posted by demelode View Post
    Bah I wrote out a whole thing and hit Go Advanced by accident. Let's try this again...

    I am following what your saying here. The total size of S(n+1) was proven to be 2^(n+1), and now the amount of evens to be 2^n. My confusion is - how does this attach to the goal of proving P(n+1) is true? Shouldn't the amount of evens be 2^(n-1) for it to be true, or am I missing something?
    I just did it.
    I proved that if there are 2^{n-1} evens in S(n)
    then there are 2^{n} evens in S(n+1).
    That is the inductive step.

    If P(n) is true then P(n+1) is true.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2011
    Posts
    8

    Re: Dealing with Binary Sequences Using PMI2 & Simple Set Theory

    Quote Originally Posted by Plato View Post
    I just did it.
    I proved that if there are 2^{n-1} evens in S(n)
    then there are 2^{n} evens in S(n+1).
    That is the inductive step.

    If P(n) is true then P(n+1) is true.
    Okay, thank you very much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simple Binary Operations Question
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: September 21st 2011, 03:51 PM
  2. dealing with the polya theory of counting
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 13th 2010, 09:01 PM
  3. Replies: 0
    Last Post: April 13th 2010, 08:37 PM
  4. Very simple Binary Relation definition needed
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 29th 2009, 03:18 AM
  5. Group Theory & Binary Operations
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 25th 2009, 01:06 PM

Search Tags


/mathhelpforum @mathhelpforum