I am working on this question
If $A$ is a set and $k\in \mathbb {N}$, let $mathscr P_k$ be the set of all subsets of $A $ that have k elements. Prove $\mathscr P_k (A)$ has ${n \choose k} $ elements
This question suppose to prove by induction, I know the base case is: if n=0, set $A$ has no elements, $\mathscr P_0$ has one element which is $\{\emptyset\}$.
I get stuck at the induction hypothesis and less of the proof.
My induction hypothesis is: suppose $A$ has $n$ elements, then $\mathscr P_k (A)$ has${n+1 \choose k} $ elements. This is not right, because $k\in \mathbb N$, I need to consider $k$.
Can anyone give me a hit or suggestion ?
Thanks
I think the induction step is on $k$, so we're considering a fixed set $A$ with fixed $n$ elements, and considering all subsets of size $k$ for $k = 0, 1, \dots, n$. So the base case is all subsets of size 0, for which the only option is $\varnothing$, so we have $1 = {n \choose 0}$ subsets of size 0.
For the induction step, we assume that there are ${n \choose k-1} = \frac{n!}{(n-k+1)!(k-1)!}$ subsets of size $k-1$, and consider the number of subsets of size $k$. All subsets of size $k$ can be obtained by adding an element to one of the $(k-1)$-element sets. So for each of the ${n\choose k-1}$ sets above, we can create $n-(k-1)$ new sets (i.e. choosing an element from the remaining). But this overcounts by a factor of $k$, since the same $k$-element set can be obtained from $k$ different $(k-1)$-element sets; namely, the set with the first element removed, second element, removed, ..., last element removed. Thus, we have:
Number of $k$-element subsets = $\frac{n!}{(n-k+1)!(k-1)!}\cdot \frac{n-k+1}{k} = \frac{n!}{(n-k)!k!} = {n\choose k}$
and so our proof is complete.