0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – imc Jul 12 '16 at 16:37
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jul 12 '16 at 19:07
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.