Problem to prove by induction:
If $ S $ is a finite set, then $\vert 2^S \vert = 2^{\vert S \vert}$
Proof:
Induction on size of $S$, call it $n$ , $n \ge 0$.
Base case: Suppose $n=0$. Now, $|2^S| = \vert\{\emptyset\}\vert = 1 $ and $2^{\vert S \vert} = 2^0 = 1 $ so base case works.
Inductive Hypothesis: Assume $\vert 2^S \vert = 2^{\vert S \vert}$ for set $S$ of size $k \ge 0$.
Inductive Step: We want to show that $S'$ of size $k+1$ has $2 ^{k+1}$ elements.
S' has one more element than S, let's call it $x$. We know $S$ has size $2^k$ so,
$S' = S $ + $($extra subsets with $ x $$)$
$\vert S\ |= 2^k +$ number of subsets with $x$ ; by Inductive Hypothesis
Number of subsets with x is also $2^k$,so
$\vert S\ |= 2^k + 2^k = 2(2^k) = 2^{k+1}$
My misunderstanding is this line: Number of subsets with $x$ is also $2^k$ How can we assume this? How is it possible to deduce this without "making it up" or how to justify this line?
Thank you anyone that helps. It's been a while since I did proofs and trying to do a bit of review and exercises. I got this proof from: Answer
Each subset of $S'$ that contains $x$ has all other elements from $S$. Each such subset, thus, can be written as the union of a unique subset of $S$ and the set $\{x\}$. Moreover, no two distinct subsets of $S$ will generate the same subset of $S'$ on union with $\{x\}$. This means that the number of subsets of $S'$ containing $x$ is equal to the number of subsets of $S$.