# Proving an Identity using Combinatorial Arguments

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

• Objection: if elements can be in one of $S_1$ or $S_2$, this is two options, not one. Hint: why are you choosing $k$ elements in the first place? – David Jan 21 at 1:33

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.