To show that for $n\geq 1$ Each $n$ element set has $2^{n-1}$ subsets of even and odd size each

73 Views Asked by At

So for this, I wrote a different proof than the one given in the textbook I'm studying discrete math from. I was wondering if it was a correct proof because I really like it and want to know if it has any logical pitfalls.

Let us consider the expansion of $$(1+x)^n= \binom{n}{0} x^n + \binom{n}{1}x^{n-1} + \ldots + \binom{n}{n-1}x^{1} + \binom{n}{n}x^0$$ Clearly, this contains every power of $x$ from $0$ to $n$. Now this can be seen as the set containing $n$ elements being partitioned into subsets if all sizes from size $0$ to $n$. For the purposes of this paper we are not concerned with the elements in the subsets only the size. The coefficients $\binom{n}{k}$ in the expansion of $(1+x)^n$ are the number of subsets with $k$ elements if we group them only by size. Now, the rest of the proof follows simply, we know that,
$$(x+1)^n= \binom{n}{0} x^n + \binom{n}{1}x^{n-1} + \ldots + \binom{n}{n-1}x^{1} + \binom{n}{n}x^0$$ Putting, $x=1$ in this equation, we get, $$(2)^n= \binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n-1} + \binom{n}{n}$$ Or, $$2^n = \sum^{i=n} _{i=0} \binom{n}{i}$$ Also, putting $x=-1$ we get, $$0= \binom{n}{0} - \binom{n}{1} + \ldots - \binom{n}{n-1} + \binom{n}{n}$$ Or, $$0= \sum^{i=n} _{i=0} (-1)^i\binom{n}{i}$$ Now adding the two equations, we get, $$2^n = 2\cdot \sum^{i=n} _{i=0,i\neq 2k+1 \forall k =(0,1\ldots \lfloor {\frac{n-1}{2}}\rfloor)} \binom{n}{i}$$ That is the sum of the even coefficients is $2^{n-1}$ which is the same as saying that the sum of all the subsets having an even number of elements (total number of subsets having an even number of elements) is $2^{n-1}$ and now putting this back into the first equation,
$$0= \binom{n}{0} - \binom{n}{1} + \ldots - \binom{n}{n-1} + \binom{n}{n}$$ We get, the sum of the odd coefficients, or total number of subsets with odd number of elements is also $2^{n-1}$

1

There are 1 best solutions below

0
On

Yes, it is OK.

And for odd $n$ you can simply see that map which maps from a family of odd power subsets of $N$ to a family of even power subset of $N$ , defined by $$X\mapsto N\setminus X$$ is a bijection and thus a conclusion.

For $N$ with even power is a little more to work.