Finding the generating function of a recurrence relation in dependence of a variable Given this inhomogeneous linear recurrence relation of 2nd order : 
$F_n = F_{n-2} + a$ for $n \geq 2$ 
with $F_1 = 1$ and $F_0 = 0$
How do I find the generating function of this recurrence relation in dependence of the variable a? I tried solving it but the solution that I got ($\frac{x + a \cdot x^2}{1-x^2} + \frac{a}{1-x}$) doesn't seem to be right. I hope someone can help.
 A: It’s easy enough to derive a closed form directly from the recurrences:
$$\begin{align*}
F_{2n}&=an\\
F_{2n+1}&=an+1
\end{align*}$$
Thus,
$$\begin{align*}
\sum_{n\ge 0}F_{2n+1}x^{2n+1}&=\sum_{n\ge 0}(an+1)x^{2n+1}\\
&=x\sum_{n\ge 0}anx^{2n}+\sum_{n\ge 0}x^{2n+1}\\
&=x\sum_{n\ge 0}F_{2n}x^{2n}+\frac{x}{1-x^2}\;,
\end{align*}$$
so
$$\begin{align*}
\sum_{n\ge 0}F_nx^n&=\sum_{n\ge 0}F_{2n}x^{2n}+\sum_{n\ge 0}F_{2n+1}x^{2n+1}\\
&=(1+x)\sum_{n\ge 0}anx^{2n}+\frac{x}{1-x^2}\\
&=a(1+x)\sum_{n\ge 0}nx^{2n}+\frac{x}{1-x^2}\\
&=\frac{a}2(1+x)x\sum_{n\ge 0}2nx^{2n-1}+\frac{x}{1-x^2}\\
&=\frac{a}2(1+x)x\frac{d}{dx}\left(\sum_{n\ge 0}x^{2n}\right)+\frac{x}{1-x^2}\\
&=\frac{a}2(1+x)x\frac{d}{dx}\left(\frac1{1-x^2}\right)+\frac{x}{1-x^2}\\
&=\frac{ax^2(1+x)}{(1-x^2)^2}+\frac{x}{1-x^2}\\
&=\frac{ax^2}{(1-x)(1-x^2)}+\frac{x}{1-x^2}\\
&=\frac{(a-1)x^2+x}{(1-x)(1-x^2)}\;.
\end{align*}$$
A: You can split this 2nd order recurrence relation into two 1st order recurrence relations. Define $b_0=0$ and $b_n=b_{n-1}+a$ for $n\geq 1$. In the same way define $c_0=1$ and $c_{n}=c_{n-1}+a$ for $n\geq 1$. Now we get 
$F_{2n}=b_n$ and $F_{2n+1}=c_n$, the first couple of terms of the generating function look like
$$
F_0 + F_{1} x + F_{2} x^2 + F_{3} x^3 + \cdots = b_0 + c_0 x + b_1 x^2 + c_1 x^3 + \dots. 
$$
If you let $B(x), C(x)$ and $F(x)$ correspond to the generating functions of $b_n,c_n$ and $F_n$ respectively you see that 
$$
F(x) = B(x^2) + x\cdot C(x^2).
$$
You can easily solve $b_n= a\cdot n$ from which you should be able to get
$$
B(x)= \frac{a x}{(x-1)^2}.
$$
The other recurrence relation can just as easily be solved as $c_n=1+a\cdot n.$ So we get
$$
C(x) = (1 + x^2 + x^3 + \cdots) + B(x) = \frac{1}{1-x} + \frac{a x}{(x-1)^2}.
$$
Now put it all together
$$
F(x) = \frac{a x^2}{(x^2-1)^2} + x\left(\frac{1}{1-x^2} + \frac{a x^2}{(x^2-1)^2}\right).
$$
This can be simplified to 
$$
F(x)=\frac{x \left((a-1) x+1\right)}{(x-1)^2 (x+1)}.
$$
