Finding the generating function of a recurrence relation in dependence of a variable

Question

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.

Answer 1

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

Answer 2

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