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.

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