# 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

-
It seems easier to break into two parts. Then each gives a quadratic. Just take say the even indices, calculate, without simplifying, $a_0$, $a_2$, $a_4$, $a_6$. –  André Nicolas Jul 14 '12 at 14:36
Namely, split into $b_n=a_{2n}$ and $c_n=a_{2n-1}$. –  anon Jul 14 '12 at 14:37
I think you mean $n\ge2$. –  KennyTM Jul 14 '12 at 17:35

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*}

-
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$.