Question

Prove that number of subsets of a set containing $n$ distinct elements is $2^n$, for all $n\in N$.

Answer 1

To prove:
Number of subsets of a set containing $n$ distinct elements is $2^n$, for all $n\in N$.

Assume given statement,
Let the given statement is $P\left(n\right)$ : Number of subsets of a set containing $n$ distinct elements is $2^n$ for all $n\in N$.
Check that statement is true for $n=1$
Assume a singleton set $i.e.,A=\left\{a\right\}$
The subsets of set $A$ are $\varphi$ and $\left\{a\right\}$
$\therefore$ Number of subsets is $2=2^1$
$\Rightarrow P\left(1\right)$ : Number of subsets of a set
have only one element is $2^1$.
Hence, $P\left(n\right)$ is true for $n=1$.

Assume $P\left(k\right)$ to be true and then prove $P(k+1)$ is true.
Assume that $P\left(n\right)$ is true for $n=k$
$\therefore$ Number of subsets of a set containing $k$ distinct element is $2^k$.
So, number of subsets of set containing $(k+1)$ distinct element $=2\times 2^k$ (Double of subsets of a set containing $k$ distinct elements)
Number of subsets of set containing $(k+1)$ distinct element $=2^{k+1}$

Thus $P(k+1)$ is true whenever $P\left(k\right)$ is true.

Hence, By Principle of mathematical Induction $P\left(n\right)$is true for all natural numbers $n$.