Counting the number of subsets of a set of 2n elements satisfying some conditions. Let $X =\{v_1, v_2,\cdots, v_n, v_{n+1},\cdots, v_{2n}\}$ be a set of $2n$ elements. I want to find the number of subsets of $X$ with $n$ elements such that both $v_i$ and $v_{n+i} $ are not together in this subset. 
I tried some small cases with $n=2,3,4$ and think it should be $2^n$ but I would like to prove it rigorously. I'm not sure how to use induction here. Is there a good combinatorial argument that can be used? Is my guess even correct? 
Thank you. 
 A: You have set the requirement for subsets that do not contain both $v_i$ and $v_{n+i} $.
However, in order for such a subset to have $n$ elements, it is clear that it must contain one of these.
As such, every subset can be generated by combining all those choices between $v_i$ and $v_{n+i} $. Each of those choices is binary, and there are $n$ choices, giving a total of $2^n$ alternative subsets that meet the conditions.
A: Using inclusion-exclusion we obtain immediately
$$2^{2n} + \sum_{k=1}^n {n\choose k} (-1)^{k} 2^{2n-2k}
= \sum_{k=0}^n {n\choose k} (-1)^{k} 2^{2n-2k}
= (-1+4)^n 
\\ = 3^n.$$
Remark. This  is for  the case of  the subsets not  containing the
forbidden pairs  having any size.  We now do  the case of  the subsets
containing $n$ elements, with the same forbidden pairs.
Using inclusion-exclusion we once more obtain immediately
$${2n\choose n} + 
\sum_{k=1}^{\lfloor n/2\rfloor} 
{n\choose k} (-1)^{k} {2n-2k\choose n-2k}
= \sum_{k=0}^{\lfloor n/2\rfloor} 
{n\choose k} (-1)^{k} {2n-2k\choose n-2k}.$$
There are several possibilities to evaluate this, one is to use the Egorychev method and introduce
$${2n-2k\choose n-2k}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n-2k+1}} (1+z)^{2n-2k} \; dz.$$
Observe that  this vanishes when $2k\gt  n$ so we may  raise the upper
limit of the sum to $n$, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{2n}
\sum_{k=0}^n {n\choose k} (-1)^k \frac{z^{2k}}{(1+z)^{2k}}
 \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{2n}
\left(1-\frac{z^2}{(1+z)^2}\right)^n
 \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
(1+2z)^n
 \; dz
= 2^n.$$
A: WLOG, $\{v_1,..v_2n\}=\{0,...,2n-1\}=2n$ (by the Von-Neumann ordinal convention of $k=\{0,..,k-1\}$). 
Our chosen set is determined by its intersection with $n$ which is an arbitrarily chosen element of the powerset $P(n)$ with cardinality $2^n$.
