Given a set $A =\{-n,-n+1,\ldots,-2,-1,1,2,\ldots,n-1,n \}$ (note that $0$ is not an element in $A$), find the recurrence relation $a(n)$ such that $a(n)$ is the subsets of $A$ that doesn't have a consecutive positive integers and doesn't have opposite numbers. (opposite numbers is any 2 numbers such that if u sum them u will get a zero.)
I tried for at least 1-2 hours and got it wrong...
I know that:
All the subsets of $\{-n,-n+1,...,-1\}$ are $2$ to the power of $n$.
All the subsets of $\{1,3,5,...,n\}$ are $2$ to the power of $(n/2)$.
All the subsets of $\{2,4,6,...,n\}$ is $2$ to the power of $(n/2)$
But I don't know how to analyze subsets that include negative integers, and non-consecutive positive integers.
can anyone guide me?
For a given $n$, divide the valid subsets of $\{-n, \ldots, n\}$ of into two groups, those which contain the element $n$ and those which do not.
How many sets contain $n$? If a valid set contains $n$ then it necessarily excludes $n-1$ as well as $-n$. We may freely choose to keep or omit $-(n-1)$, and having excluded $n-1$ we are free to choose the remaining subset of $\{-(n-2), \ldots, n-2\}$ in any valid manner. Therefore the number of valid subsets of $\{-n, \ldots, n\}$ is exactly $2a(n-2)$.
Now carry out similar logic to count the other case where $n$ is excluded and we may choose to include or exclude $-n$ without restriction. Since the two cases are exhaustive and mutually exclusive, you will then get the exact count for $a(n)$ by summing the two counts, and this will give the desired recurrence relation.
It is common to adopt the convention that $a(0)=1$: this encodes the fact that there is exactly one subset of the empty set which satisfies both constraints (the empty set itself, of course). As a spot check, note that the number of valid subsets of $\{-2, -1, 1, 2\}$ which contain the element $2$ is exactly $2$, which agrees with the expression $2a(0)$ calculated above.