Call an element a diverse if there is a red set containing $a$, a red set not containing $a$, a blue set containing $a$, and a blue set not containing $a$. We consider two cases based on whether a diverse element exists. We use $A\Delta B$ to denote the symmetric difference of sets $A$ and $B$.

Case 1: Suppose no element $a$ is diverse. We now show that if $R, R'$ are two distinct red sets and $B, B'$ are two distinct blue sets, then $R\Delta B \neq R'\Delta B'$. Since $R, R'$ are distinct, there is an element $s$ in one and not the other. Since $s$ is not diverse, $s$ is in both $B, B'$ or in neither of $B, B'$. Either way $s$ will lie in exactly one of $R\Delta B$ and $R'\Delta B'$, so the two cannot be equal. Thus, all of the symmetric differences of red sets and blue sets are distinct. If there are $r$ red sets and $b$ blue sets, then $r+b = 2^n+1$, so there are at least $rb \geq 2^n \cdot 1 = 2^n$ symmetric differences.

Case 2: Suppose there is an element $a$ that is diverse. Let $R_0$ be the set of red sets that do not contain $a$, $R_1$ be the set of red sets that do contain $a$, $B_0$ the set of blue sets that do not contain $a$, and $B_1$ the set of blue sets that do contain $a$. By the diversity of $a$ all four of these sets are non-empty.

By the pigeonhole principle, one of $R_0 \cup B_0$ or $R_1 \cup B_1$ has at least $2^{n-1} + 1$ sets. Without loss of generality, let it be $R_0 \cup B_0$. Apply the inductive hypothesis to obtain a set $A_0$ of at least $2^{n-1}$ distinct sets that are the result of symmetric differences between $R_0$ and $B_0$. Likewise, by the pigeonhole principle one of $R_0 \cup B_1$ or $R_1 \cup B_0$ has at least $2^{n-1} + 1$ sets. Without loss of generality, let it be $R_0 \cup B_1$. Apply the inductive hypothesis to obtain a set $A_1$ of $2^{n-1}$ distinct sets that are the result of symmetric differences between $R_0$ and $B_1$.

Notice that all of the sets in $A_0$ do not contain $a$ while all of the sets in $A_1$ do contain $a$. Therefore, $A_0$ and $A_1$ together contain $2^n$ distinct sets obtained from the symmetric difference of red sets and blue sets, completing the induction.