Task from old exam:
$|S|$ is the amount of elements in a finite set $S$ and $$P_{0}(S)= \left\{N \subseteq S: |N| \text{ is even}\right\}$$ $$P_{1}(S)= \left\{N \subseteq S: |N| \text{ is uneven}\right\}$$
Prove by induction: For every non-empty set S we have that: $|P_{0}(S)|=|P_{1}(S)|$
I wouldn't be sure how to prove this but I would go for induction. First show that the satement works for $S$ and then if it worked for $S$ show that it will work for every other, so for
$$S'= S\cup \left\{x\right\}, x \notin S$$ but then there is a problem, on which set we need to look at to prove this via induction? Or maybe this way is just bad/impossible here..?
Maybe on these sets would work? $$\left\{N \in P_{j}(S'): x \in N\right\}$$ and then also for $$\left\{N \in P_{j}(S'): x \notin N\right\}$$ where $j \in \left\{0,1\right\}$
This would be the idea how I would do it but there is a better, easier way maybe?
Sketch: Induction is the right way to go.
Base case: If $|S|=1$, then $S=\{x\}$ and there are two subsets of $S$, $\emptyset$ and $\{x\}$. We see that $P_0(S)=\{\emptyset\}$ and $P_1(S)=\{\{x\}\}$ since the empty set has zero elements (an even number).
Inductive case: Suppose that the claim is true for sets of size $k\geq 1$ and let $|S|=k+1>1$. Fix $x\in S$ and let $S'=S\setminus\{x\}$. By the inductive hypothesis, $|P_0(S')|=|P_1(S')|$.
Now, what is $P_0(S)$ and $P_1(S)$? Let's focus on $P_0(S)$. Suppose that $T\in P_0(S)$; then $|T|$ is even. If $x\not\in T$, then $T\subseteq S'$, so $T\in P_0(S')$. On the other hand, if $x\in T$, then let $T'=T\setminus \{x\}$. We know that $T'\subseteq S'$ and $|T'|=|T|-1$, so $|T'|$ is odd, so $T'\in P_1(S')$. Therefore, $|P_0(S)|=|P_0(S')|+|P_1(S')|$.
By a similar argument, $|P_1(S)|=|P_0(S')|+|P_1(S')|$.