数列{a_n}の母関数をF(z)とおけば、与えられた漸化式から
F(z)-1=zF(z)+(1/2)(z/(1-z)-(-z)/(1+z))
となるのでこれをF(z)について解いておしまい。

二項定理を使った解答がお好きなら勝手にやってね。