Counting subsets. I know we can use induction to prove statements about counting various types of subsets of a set and that we have to apply  the same idea to count the number of pairs of disjoint subsets of a set.
I am given with the following definitions:


*

*$(S_{n})$: Let $n∈N$. We define the set $S_{n} = \{0, 1, . . . , n−1\}$ (with $S_{0}$ obviously $= ∅$). Note that $|S_{n}| = n$.

*$(DP_{n})$: Let $n∈N$. We define the set of disjoint subset pairs of $S_{n}$ as: $$ DP_{n}=\{(A, B) \ | \ A, B ⊆ S_{n} \ \text{and} \ A ∩ B = ∅\} $$


From this I've inferred for $n = 0$, $S_{n} = ∅$, and $DP_{n} = \{(∅, ∅)\}$. For $n = 3$, $S_{n}= \{0, 1, 2\}$, some elements of $DP_{3}$ are $(\{1\}, \{0, 2\})$ and $(\{0, 1, 2\}, ∅)$ and that order matters in tuples so the pair $(\{0, 2\}, \{1\})$ in $DP_{3}$, and is considered different from $(\{1\}, \{0, 2\})$. Please correct me if any of these assumptions is wrong.
(a) What are $DP_{1}$ and $DP_{2}$ explicitly in set notation?
(b)  Find a formula for the size of $DP_{n}$ (in terms of $n$), and then prove that your formula is correct for all values of $n$ ($\forall n \in \mathbb{N}$).
 A: 
From this I've inferred for $n = 0$, $S_{n} = ∅$, and $DP_{n} = \{(∅,
> ∅)\}$. For $n = 3$, $S_{n}= \{0, 1, 2\}$, some elements of $DP_{3}$
  are $(\{1\}, \{0, 2\})$ and $(\{0, 1, 2\}, ∅)$ and that order
  matters in tuples so the pair $(\{0, 2\}, \{1\})$ in $DP_{3}$, and is considered different from $(\{1\}, \{0, 2\})$.

Yes, this is correct.
(a) Start from $S_0=\{\}$,  $DP_0 = \{(\emptyset, \emptyset)\}$ 
Add in the pairs due to new the element $0$ in $S_1=\{0\}$: 
$$
DP_1 = DP_0 \cup \{(\emptyset,0), (0,\emptyset) \}
$$
Similarly, the pairs due to the new element $1$ in $S_2=\{0,1\}$:
$$
DP_2 = DP_1\cup \{(0,1),(1,0),(1,\emptyset),...,(\{0,1 \},\emptyset) \}
$$
Note that the recursive structure of $DP_n$. This is key for an inductive proof; when you attempt it, you will see that: $|DP_n|=|DP_{n-1}|+2\cdot 3^{n-1}$
(b) This is the same formula as provided in the question linked by Ross Millikan; although I will explain a little more here. 
You could pick any $m$ elements out of $n$ to form a subset $A$ (the number of ways to do this is given by the binomial coffifient); then to form the other disjoint subset $B$, you can pick any combination of the remaining $n-m$ elements. There are $2^{n-m}$ possibilities.(Why?)
To conclude, for each subset $A$ of size $m$(of which there are $\binom{n}{m}$), there are $2^{n-m}$ disjoint subsets ($B$); and $m$ can vary from zero(when $A$ is the empty set) all the way up to $n$(when $B$ is the empty set). Thus giving us:
$$
\sum_{m=0}^{n}\binom{n}{m}2^{n-m} = \sum_{m=0}^{n}\binom{n}{m}2^{n-m}\cdot 1^m = 3^n 
$$
The final equality above follows from the binomial theorem: 
$$
(a+b)^n =\sum_{m=0}^n a^{n-m}\cdot b^m
$$
The above is a proof enough, but the way the question is phrased it looks like it's asking you to rigorously prove that that $DP_n$ has $3^n$ elements by using induction on $n$. 
Hint: Assume $DP_n$ has $3^n$ elements and count the number of subset pairs in $DP_{n+1}$that contain the new element $n$ from $S_{n+1}=\{0,1,2...n\}$. (Like in (a), above.)
Read the combinatorial proof of Pascal's identity for inspiration if required.
Hint #2: The number of subsets $A$ of size $k$ containing the new element $n$ from $S_{n+1}=\{0,1,2...n\}$ is $\binom{n-1}{k-1}$(since $n$ is already in $A$, only $k-1$ more can be picked); and $k$ can vary from $1$ to $n$. Also, for each such $A$, you can pick any combination of elements from the remaining $n-k$ elements to get $B$. In addition to that, for each $(A,B)$ you also have $(B,A)$; remember to account for that.
A: This is what I did for (b):
Let $n \in \mathbb{N}$. Then for the base case, $n=0$:
            \begin{align*}
    L.H.S.=|DP_0|=1\\
    R.H.S.=3^0=1
   \end{align*}
        So $P(0)$ holds.
Assuming that $P(k)$ holds for $n=k$, we have $|DP_k|=3^k$
And we need to prove $|DP_{k+1}|=3^{k+1}$ for $n=k+1$.
Now, \begin{align*}
    |DP_{k+1}| &=|DP_k| \cup  |\{ \text{the pairs of elements in the set $S_k$} \}|\\
    &=3^k +2.3^k && \text{(The $2$ is to account for the pairs occurring}\\
    &= 3^k(1+2) && \text{in the subsequent set being added since order}\\
    &= 3^k.3 && \text{does matter in tuples.)}\\
    &= 3^{k+1}  
  \end{align*}
        which is what we wanted to show. 
$\therefore P(k+1)$ holds.
