APPROACH 1: Trial and Error
$\rightarrow$ For $n=2$, $U={1,2}$.
$\rightarrow$ The subsets of $U$ are $\left \{ \Phi , \{1\},\{2 \}, \{1,2 \} \}\right.$
$\rightarrow$ So,set $X$ has $4$ possibilities as above.
$\rightarrow$ Seeing $x$ as element of $X$, $x$ can be $1$ or $2$ and nothing else.
$\rightarrow$ So $A$ is the set of ordered pairs where the $1^{st}$ part is an element of $X$ (it is a value of $x$) and the $2^{nd}$ part is a subset of $U$.
$\rightarrow$ There are $2$ possibilities for the $1^{st}$ part, and $4$ possibilities for the $2^{nd}$ part.
$\rightarrow$ i.e. $A$ can have: $(1,\Phi ), (1, \{1 \} ) ,(1, \{2 \}), (1,\{1,2 \}), (2,\Phi ), (2, \{1 \} ) ,(2, \{2 \}), (2,\{1,2 \})$
$\rightarrow$ Here $(1,\Phi)$ will not be considered, as $1$ $\notin$ $ \Phi$.
$\rightarrow$ Similarly, $(1, \{2 \}),(2,\Phi ),(2, \{1 \} )$ won't be considered on similar grounds.
$\rightarrow$ so $A=$ $(1, \{1 \} ), (1,\{1,2 \}),,(2, \{2 \}), (2,\{1,2 \})$
$\therefore $ $\begin{vmatrix} A \end{vmatrix} = 4$
$I.$ gives answer for $n=2$ as: $\begin{vmatrix} A \end{vmatrix} = 2*2 =4$
$II.$ gives answer for $n=2$ as: $\begin{vmatrix} A \end{vmatrix} =$ $1*^{2}C_{1}$ $+ 2 * $ $^2C_2$ $=4$
$\because$ Both $I.$ and $II.$ are True
$\therefore$ Option $C$ is the right answer.
APPROACH 2:
- To show $II.$ is correct:
$\rightarrow$ $A = \{y = (x,X)| X\ proper\ subset\ of\ U,\ x\ in X \}$.
$\rightarrow$ Lets first fix $X$. Here $X$ being proper subset of $U$, $X$ can have all values of that of a power Set of $U$.
$\rightarrow$ Lets say number of elements in $X$ is $k$.
$\because$ Number of elements of $U$ is $n$, $k$ can take values from $0$ to $n$ ($\because$ $X$ is proper subset of $U$)
$\therefore$ The number of ways of selecting $k$ from $n$ is given by $^{n}C_{k}$
$\rightarrow$ So we have $^{n}C_{k}$ choices for choosing $X$.
$\rightarrow$ Now, fixing our choice of $X$, and assuming it has $k$ elements, how many choices for $x$ are there ?
$\rightarrow$ There are $k$ different elements in $X$, so there are $k$ choices for choosing $x$
$\rightarrow$ For eg $X= \{1,2,3 \} $, then $x$ can be $1$ or $2$ or $3$, as only these $3$ elements belong to $X$.
$\rightarrow$ So for a given $k$, there are $k* ^{n}C_{k}$ choices of $(x,X)$ such that $\begin{vmatrix} X \end{vmatrix} = k$
$\rightarrow$ So how many elements $y$ are there in total?
$\rightarrow$ Sum the above for $k =1$ to $n$. $k$ can't be $0$ because if $X$ has $0$ elements, then $x$ doesn't exist.
$\rightarrow$ i.e.$\begin{vmatrix} A \end{vmatrix}$ = $\sum_{k=1} ^{n} k \binom{n}{k}$
- To show the formula for $I.$ is correct:
$\rightarrow$ Consider choosing an element $x$ in our pair $(x,X)$. There are $n$ choices for $x$.
$\rightarrow$ Then we ask ourselves how many valid choices of $X$ are there, given $x$ ?
$\rightarrow$ $X$ is entirely defined by its elements, and we have a finite list of potential elements $(1$ to $n)$.
$\rightarrow$ For each of these, an element is either in or out, giving us $2$ possibilities each time but $x$ is already fixed to be included in $X$ for it to belong in $X$ .
$\because$ out of $n$ elements, only $x$ has $1$ choice to be included, and all the other $n-1$ elements can have $2$ possibilities as to be included or excluded in $X$.
$\because$ Its an ordered pair, we need both these conditions happening together, so using $product\ rule$ we arrive at $n*2^{n-1}$ choices for $(x,X)$.
$\because$ Both $I.$ and $II.$ are True
$\therefore$ Option $C$ is the right answer.
