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

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

• Is this the general way to go about solving inhomogeneous recurrence relations? I just haven't found a method that is applicable to all problems. – imc Jul 12 '16 at 16:37
• @imc: No, this was simply the first approach that occurred to me for this particular problem. There are some recurring themes and approaches, but what I end up using definitely depends on the specific problem. – Brian M. Scott Jul 12 '16 at 19:07

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