Take the 2-minute tour ×  I am self-studying Discrete
Mathematics, and I have the following question:  Let $X$ be a
set with exactly $n$ distinct elements. How many elements does
have $\mathcal{P}(X)?$  I know that there are $2^{n}$ subsets. I
know how to prove it by using induction on $n$, but I want to
solve this question by counting all the elements in
$\mathcal{P}(X).$ I am not allowed to use the binomial theorem,
or binomial coefficients because they were not defined yet. Is
that possible?  share|improve this question add comment  2
Answers  up vote 2 down vote accepted  It is. Let
$X=\{x_1,\dots,x_n\}$. Now imagine that you are choosing a
subset of $X$ by running through the list $x_1,\dots,x_n$ and
saying yes, you're in my set or no, you're not in my set to each
$x_k$ in turn. You will make $n$ choices, and each of those
choices can be made in $2$ ways, so there are altogether $2^n$
ways to make the string of choices. Thus, there are $2^n$
possible subsets of $X$ to choose.  share|improve this answer a