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 , let denote the set of all binary sequences of length . For example, = { (0, 0), (0, 1), (1, 0), (1, 1) } (for each positive integer , contains elements). **__Use mathematical induction__ to prove that for every positive integer , there are exactly 2^(n−1) elements of that contain an even number of entries equal to 1. For example, in , 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 has 2 = 2^(2−1) sequences with an even number of entries equal to 1.

Answer: Let denote the predicate "Every set of binary sequences of length 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) is True.

(2) For all n, n >= 1 [ , , , ... ] ->

(1) : = {(0), (1)}. In , 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, is True.

(2) To prove (2), let n >= 1 be such that [ , , , ... ] 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! :D

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

Quote:

Originally Posted by

**demelode** Question: [B]For each positive integer

, let

denote the set of all binary sequences of length

.

__Use mathematical induction__ to prove that for every positive integer

, there are exactly 2^(n−1) elements of

that contain an even number of entries equal to 1.

Answer: Let

denote the predicate "Every set of binary sequences of length

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 is formed by taking a string from and adding a 0 to get a new one in and adding 1 to another.

If you note .

There are strings in with an odd number of 1's. If we add a 1 to each of those we get a string in with an even number of 1's.

So how many new strings are there?

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

Quote:

Originally Posted by

**Plato** Here is the idea. Every string is

is formed by taking a string from

and adding a 0 to get a new one in

and adding 1 to another.

If you note

.

There are

strings in

with an odd number of 1's. If we add a 1 to each of those we get a string in

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.

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

Quote:

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 also give a string in with an even number of 1's.

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

Quote:

Originally Posted by

**Plato** Also do not forget that by a 0 to a string with an even number of 1's in

also give a string in

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?

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

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

Quote:

Originally Posted by

**Plato** By adding a 1 to all the odds in

we get

evens in

.

By adding a 0 to all the evens in

we get

evens in

.

Now

evens in

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?

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

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

Quote:

Originally Posted by

**Plato** **I just did it.**
I proved that if there are

evens in

then there are

evens in

.

That is the inductive step.

If

is true then

is true.

Okay, thank you very much!