Build recurrence relation from a Combinatorial problem 
$a_n$ is the number of sub sets of $A=[{-n,...,-1,1,...,n}]$.
The sub sets doesn't contains:
  
  
*
  
*Two positive consecutive numbers.
  
*Opposite numbers.
  
  
  Note: $0\notin A$
Build recurrence relation and find initial conditions for $a_n$.

How do I approach this specific question? Is there a step-by-step approach to solve this kind of questions? 
 A: I can’t give you a recipe, but I can work this problem in enough detail to show how I’d go about attacking such a problem.
Let $S_n = \{-n,\dots,-1,1,\dots,n\}$; $a_n$ is the number of ‘allowable’ subsets of $S_n$. The basic idea is to try to see what happens when we go from $S_n$ to $S_{n+1}$.
For starters, every allowable subset of $S_n$ is still an allowable subset of $S_{n+1}$; that accounts for $a_n$ allowable subsets of $S_{n+1}$. $S_{n+1}$ also has allowable subsets that contain $-(n+1)$; how many? If $A$ is any allowable subset of $S_n$, then $A\cup\{-(n+1)\}$ is an allowable subset of $S_{n+1}$, and if $A$ is any allowable subset of $S_{n+1}$ that contains $-(n+1)$, then $A\setminus\{-(n+1)\}$ is an allowable subset of $S_n$, so $S_{n+1}$ has $a_n$ allowable subsets that contain $-(n+1)$. Finally, $S_{n+1}$ also has allowable subsets that contain $n+1$ (but not, of course, $-(n+1)$). These are the hardest to count, because we can’t just add $n+1$ to an allowable subset of $S_n$: we can only add $n+1$ to those allowable subsets of $S_n$ that don’t contain $n$.
Temporarily let $b_n$ be the number of allowable subsets of $S_n$ that don’t contain $n$. We’ve just seen that $a_{n+1} = 2a_n+b_n$, so we’ll have the desired recurrence if we can express $b_n$ in terms of $a_n$ and perhaps some other $a_k$’s with $k<n$. Let $A$ be an allowable subset of $S_n$ that doesn’t contain $n$. If $-n\notin A$, then $A$ is actually an allowable subset of $S_{n-1}$. Conversely, every allowable subset of $S_{n-1}$ is an allowable subset of $S_n$ that doesn’t contain $n$, so $S_n$ has $a_{n-1}$ allowable subsets that contain neither $n$ nor $-n$. What if $-n\in A$? Then $A\setminus\{-n\}$ is an allowable subset of $S_{n-1}$. Conversely, if $A$ is an allowable subset of $S_{n-1}$, then $A\cup\{-n\}$ is an allowable subset of $S_n$ that contains $-n$ but not $n$. Thus, there are also $a_{n-1}$ allowable subsets of $S_n$ that contain $-n$ but not $n$. It follows that $b_n = 2a_{n-1}$ and hence that $a_{n+1} = 2a_n +2a_{n-1}$.
This is a second-order recurrence, so for initial conditions we need to specify both $a_1$ and $a_2$. The only forbidden subset of $S_1 = \{-1,1\}$ is $S_1$ itself; the other three subsets, $\{-1\},\{1\}$, and $\varnothing$, are all allowable. Thus, $a_1 = 3$. $S_2 = \{-2,-1,1,2\}$ has $2^4=16$ subsets, of which eight are forbidden: $S_2$ itself, all four of its $3$-element subsets, and the $2$-element subsets $\{-2,2\},\{-1,1\}$, and $\{1,2\}$. Thus, $a_2 = 16 - 8 = 8$.
At this point it’s a good idea to use the recurrence to calculate $a_3 = 2a_2+2a_1=22$ and check it by enumerating the allowable subsets of $S_3 = \{-3,-2,-1,1,2,3\}$ to verify that there are indeed $22$ of them. They are:
$$\matrix{\varnothing & \{-3\} & \{-2\} & \{-1\} & \{1\} & \{2\} & \{3\}\\
\{-3,-2\} & \{-3,-1\} & \{-3,1\} & \{-3,2\} & \{-2,-1\} & \{-2,1\} & \{-2,3\}\\
\{-1,2\} & \{-1,3\} & \{1,3\} & \{-3,-2,-1\} & \{-3,-2,1\} & \{-3,-1,2\} & \{-2,-1,3\}\\
\{-2,1,3\} &&&&&&}$$
A: Hint:


*

*Let $b_n$ be the number of subsets of $A_n$ which have $n$ as an element.  

*Let $c_n$ be the number of subsets of $A_n$ which have $-n$ as an element.

*Let $d_n$ be the number of subsets of $A_n$ which have neither $n$ nor $-n$ as elements.

*Let $e_n$ be the number of subsets of $A_n$ which have both $n$ and $-n$ as elements.


You should be able to find for example


*

*$a_n$ in terms of $b_n$, $c_n$, $d_n$ and $e_n$

*$b_n$, $c_n$, $d_n$ and $e_n$ in terms of $b_{n-1}$, $c_{n-1}$, $d_{n-1}$ and $e_{n-1}$


Now eliminate $b,c,d,e$.  
Note that you start with $a_0=1$ (the empty set) and $a_1=3$ ({ }, {1}, {-1}). 
Added (since Brian has given a fuller answer):


*

*$a_n = b_n +c_n + d_n - e_n$

*$e_n = 0$

*$c_n  = b_{n-1}+c_{n-1}+ d_{n-1}= a_{n-1}$

*$d_n = b_{n-1}+c_{n-1}+ d_{n-1}= a_{n-1}$

*$b_n = c_{n-1}+ d_{n-1}$


So $a_n=c_{n-1}+ d_{n-1} + a_{n-1} +a_{n-1} -0 = 2a_{n-1}+2a_{n-2}$.
This is OEIS A028859 and has the closed form $$\frac{(1+\sqrt{3})^{n+2}-(1-\sqrt{3})^{n+2}}{4\sqrt{3}}.$$
