A set $A$ has $n$ elements. A subset of $P$ of $A$ is chosen (with replacement) and another subset $Q$ is chosen. Find number of ways of choosing $P$ and $Q$ such that $P\cap Q=\emptyset$
If $n(P)=0$, number of subsets $Q=^nC_0+^nC_1+\cdots +^nC_n=2^n$
If $n(P)=1$, then number of subsets $Q=^nC_0+^nC_1+\cdots +^nC_{n-1}$
Adding all the cases, number of ways is $(n+1)\cdot^nC_0+n\cdot^nC_1+\cdots ^nC_n$
But answer given is $3^n$.
(I have already seen two posts on SE regarding the same question but not this method. What is the mistake I am making?)
Best Answer
For the case $n(P)=1$, you should have $${{n−1}\choose 0}+{{n−1}\choose 1}+\cdots+{{n−1}\choose {n−1}}=2^{n-1}$$ because you are not allowed to include any elements of $P$ (of which there is $1$) when you choose elements for $Q$. So in general, when $n(P)=k$, the number of possibilities for $Q$ is $${{n-k}\choose 0}+{{n-k}\choose 1}+\cdots+{{n-k}\choose{n-k}}=2^{n-k}$$ because there are $k$ elements (the elements of $P$) that you must exclude when choosing elements for $Q$.
Now when you add all the cases, it's not clear where the numbers are coming from. How do you get the coefficients $n+1$ and $n$ and so on? You should add up over all the cases (which are disjoint) the number of possibilities for $P$ times the number of possibilities for $Q$. When $n(P)=k$, there are $n \choose k$ possibilities for what the set $P$ is. We already computed that there are $2^{n-k}$ possibilities for $Q$ given $P$. So in total there are ${n\choose k}\cdot 2^{n-k}$ possibilities for $P$ and $Q$ when $n(P)=k$. So the answer is $$\sum_{k=0}^n{n\choose k}\cdot 2^{n-k}=3^k.$$ (You can use the binomial theorem to compute this sum.)