Dealing with Binary Sequences Using PMI2 & Simple Set Theory

**demelode** · September 24th 2011, 05:32 AM

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 ﬁrst 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!

**Plato** · September 24th 2011, 06:03 AM

Originally Posted by demelode

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?

**demelode** · September 24th 2011, 06:15 AM

Originally Posted by Plato

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.

**Plato** · September 24th 2011, 06:34 AM

Originally Posted by demelode

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.

**demelode** · September 24th 2011, 06:44 AM

Originally Posted by Plato

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?

**Plato** · September 24th 2011, 07:09 AM

Originally Posted by demelode

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)$

**demelode** · September 24th 2011, 07:19 AM

Originally Posted by Plato

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?

**Plato** · September 24th 2011, 07:30 AM

Originally Posted by demelode

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.

**demelode** · September 24th 2011, 07:33 AM

Originally Posted by Plato

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!

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

LinkBack

Thread Tools

Display

Dealing with Binary Sequences Using PMI2 & Simple Set Theory

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

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

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

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

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

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

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

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

Similar Math Help Forum Discussions

Simple Binary Operations Question

dealing with the polya theory of counting

exponential generating function dealing with # of n-digit sequences

Very simple Binary Relation definition needed

Group Theory & Binary Operations

Search Tags