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

Answer: Let $\displaystyle P(n)$ denote the predicate "Every set of binary sequences of length $\displaystyle 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) $\displaystyle P(1)$ is True.

(2) For all n, n >= 1 [$\displaystyle P(1)$, $\displaystyle P(2)$, $\displaystyle P(3)$, ... $\displaystyle P(n)$] -> $\displaystyle P(n+1)$

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

(2) To prove (2), let n >= 1 be such that [$\displaystyle P(1)$, $\displaystyle P(2)$, $\displaystyle P(3)$, ... $\displaystyle 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!