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

1. 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 ﬁ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!

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

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?

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

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.

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

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.

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

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?

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

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

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

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?

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

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.

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

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!