0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Jan 21 at 1:33
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.