Prove using induction that, $|\{B ⊆ A_n \mid 0 ∈ B\}| = 2^{n−1}$ where $A_n = \{k ∈ N \mid k < n\}$ and $n ≥ 1$

Question

So far I've found that the $n = 1$ is the base case. However, I can't seem to progress to actually proving his. If the set $B ⊆ A_n$ do I have to prove that $2^{n-1}$ applies to both the empty and singleton set (all possible subsets)? I'm also unsure on how to progress into the inductive step, would that involve creating a new set where $k = n+1$?

Answer 1

I take it that you construe $\text{“}N\text{ ''}$ to include $0$, so $A_n=\{0,1,2,\ldots,n-1\}.$

Suppose this proposition is true of $n.$ Consider this set: $$ \Big\{B : B\subseteq A_n\ \&\ 0\in B\Big\} \cup \Big\{B\cup\{n\} : B\subseteq A_n\ \&\ 0\in B\Big\}. $$ The first of the two sets whose union is taken has $2^{n-1}$ members, by the induction hypothesis. The second has exactly as many members as the first. $$ 2^{n-1} + 2^{n-1} = 2^n. $$