Solving a recurrence of a sequence The sequence $a_n$ is given by recurrence $$a_0=0,a_1=1,a_n=a_{n-2}+n+4, n>2$$ How to find the general term I am interested on different approach. Can generating functions help
 A: The recurrence can indeed be solved using generating functions. I prefer to write the recurrence as
$$a_n=a_{n-2}+n+4-4[n=0]-4[n=1]\;,$$
using Iverson brackets and assuming that $a_n=0$ for $n<0$. Then multiply through by $x^n$ and sum over $n\ge 0$ to get the generating function, $g(x)$:
$$\begin{align*}
g(x)&=\sum_{n\ge 0}a_nx^n\\
&=\sum_{n\ge 0}a_{n-2}x^n+\sum_{n\ge 0}nx^n+4\sum_{n\ge 0}x^n-4-4x\\
&=x^2g(x)+x\sum_{n\ge 0}nx^{n-1}+\frac4{1-x}-4-4x\\
&=x^2g(x)+x\left(\frac1{1-x}\right)'+\frac4{1-x}-4-4x\\
&=x^2g(x)+\frac{x}{(1-x)^2}+\frac4{1-x}-4-4x\\
&=x^2g(x)+\frac{x+4(1-x)-4(1-x)^2-4x(1-x)^2}{(1-x)^2}\\
&=x^2g(x)+\frac{4-3x-4(1+x)(1-x)^2}{(1-x)^2}\;,
\end{align*}$$
so
$$\begin{align*}
g(x)&=\frac{4-3x-4(1+x)(1-x)^2}{(1+x)(1-x)^3}\\
&=\frac{4-3x}{(1+x)(1-x)^3}-\frac4{1-x}\\
&=\frac18\left(\frac7{1+x}+\frac7{1-x}+\frac{14}{(1-x)^2}+\frac4{(1-x)^3}\right)-\frac4{1-x}\\
&=\frac18\left(\frac7{1+x}-\frac{25}{1-x}+\frac{14}{(1-x)^2}+\frac4{(1-x)^3}\right)\\
&=\frac18\left(7\sum_{n\ge 0}(-1)^nx^n-25\sum_{n\ge 0}x^n+14\sum_{n\ge 0}(n+1)x^n+4\sum_{n\ge 0}\binom{n+2}2x^n\right)\;,
\end{align*}$$
and
$$\begin{align*}
a_n&=\frac18\left(7(-1)^n-25+14(n+1)+4\binom{n+2}2\right)\\
&=\frac18\left(2n^2+20n-7+7(-1)^n\right)\\
&=\begin{cases}
\frac{n(n+10)}4,&\text{if }n\text{ is even}\\
\frac{n(n+10)-7}4,&\text{if }n\text{ is odd}\;.
\end{cases}
\end{align*}$$
A: If you define $b_n=a_n+\frac {n^2+10n}4$, the $n+4$ terms go away.  I get $a_{2n}=\frac{(2n)^2+20n}4=n^2+5n$ and $a_{2n+1}=\frac{(2n+1)^2+10(2n+1)-7}4=n^2+6n+1$.
