Proving an Identity using Combinatorial Arguments

Question

I'm working on this question:

For integers $n\geq1$, define $A_{n}$ to be the set of all ordered pairs of subsets of ${1,\dots,n}$, i.e. $$A_{n}=\{(S_{1},S_{2}) \mid S_{1},S{2} \subseteq \{1,\dots,n\}\}$$

I need to prove using combinatoric arguments that $$4^n=\sum_{k=0}^{n}{n\choose{k}}3^{n-k}$$ Here's what I have so far.

The left hand side is fairly simple, there are $2^{n}$ options for $S_{1}$ and $S_{2}$, so the total number of ways is $2^{n} \times 2^{n} = 4^{n}$.

Now for the right hand side. What I have right now is that we choose a subset of $k$ elements from $\{1,\dots,n\}$. There are $n\choose k$ ways to do this. This is where I'm getting stumped. I was thinking that the $n-k$ elements can either both not be in $S_{1}$ or $S_{2}$, be in one of $S_{1}$ or $S_{2}$, or be in both $S_{1}$ and $S_{2}$, giving us $3^{n-k}$ ways to do this. I'm not sure if this would be valid reasoning or not.

Any hints would be greatly appreciated

Answer 1

The equation is just the binomial expansion of $(1+3)^n$. One combinatorial approach is to say you choose $k$ elements to be only in $S_1$, then all the others can be in both, $S_2$ only, or neither.