How to count the number of subsets where no two elements have sum equal to $n + 1$? I'm given a set of $n$ integers, where the integers are numbered from $1$ to $n$. 
For example if $n = 3$, the set would be $\{1, 2, 3\}$. 
The question is: how many subsets don't have a pair whose sum = $n + 1$.
If I consider all subsets of $n = 3$, $\{\}$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1, 2\}$, $\{2, 3\}$, $\{1, 3\}$, $\{1, 2, 3\}$.
In this case the number of subsets in the above condition is $6$ because I excluded $\{1, 3\}$, $\{1, 2, 3\}$ and there exists a pair add up to $n + 1$, which is $(1, 3)$. I noticed that the number of pairs whose sum add up to $n + 1$ = $\lfloor{\frac{n}{2}}\rfloor$.  
 A: To make such a subset, for each of pair that sums to $n+1$, you have to decide between $3$ options: Include the only lower number, include only the higher number, or not include any of them. This gives a total of
$$
3^{\lfloor n/2\rfloor}
$$
options.
When $n$ is odd, you also have the number $\frac{n+1}2$ which is not part of any pair. This one you can freely decide whether to include.
So all in all, we get
$$
\text{Number of such subsets} = \cases{3^{n/2} & if $n$ is even\\ 2\cdot 3^{(n-1)/2} & if $n$ is odd}
$$
A: In this answer I'll do the even case, and I'll leave the odd case to you. Suppose that $n$ is even, so $n = 2k$. Then we can split $\{1,\ldots,n\}$ up into all the pairs that add up to $n + 1$:
$$
\{(1, n), (2, n-1), \ldots, (k, k+1)\}.
$$
Our condition means that when we are making a subset of $\{1,\ldots,n\}$, we cannot have both elements from a pair. And this is the only condition! Thus for each of the $k$ pairs, we can either take the first element, the second element, or neither element, for a total of $3^k$ options. In other words, when $n$ is even, there are $3^{\frac n2}$ such subsets.
