# Generating Function of a Recurrence Relation.

Given a sequence a(n) = a(n -2) , a(0) = 2 , a(1) = -1
Find the generating function

What i have done so far:
The recurrence relation is going to be a(n) - a(n-2) = 0
A = the generating function
A = 2 - x + 2x^2 - x^3 + 2x^4.......
x^2 * A = 2x^2 - x^3 + 2x^4 ..........
- subtracting the two equations.
1-x^2 A = 2 -x
divide both sides by 1-x^2
A = 2-x / 1-x^2

This is how i was taught to do it , but when u plug in numbers for x , it doesnt seem to satisfy the premise.

• Why are you plugging in numbers for $x$? What are you expecting to get back? – Brian M. Scott Dec 16 '13 at 18:50
• when you plug numbers for x , shouldnt it equal the a number in the sequence – user2036503 Dec 16 '13 at 18:52
• No, except that $A(0)=a_0$. – Brian M. Scott Dec 16 '13 at 18:53
• Think about it: why on earth should $\sum_{n\ge 0}a_nk^n$ be equal to $a_k$? – Brian M. Scott Dec 16 '13 at 18:54
• so if i plug in say x=2 , its not suppose to equal a(2)? – user2036503 Dec 16 '13 at 18:55

## 1 Answer

Your generating function is correct. What you have to realize is that a generating function is not a closed form for the sequence: it’s a function whose power series has the terms of the sequence as coefficients.

Here you can actually work backwards to check that you have the right generating function. Split it into partial fractions:

$$A(x)=\frac{2-x}{1-x^2}=\frac{1/2}{1-x}+\frac{3/2}{1+x}\;.$$

You know that $$\frac1{1-x}=\sum_{n\ge 0}x^n\;,$$

so (substituting $-x$ for $x$) $$\frac1{1+x}=\sum_{n\ge 0}(-x)^n=\sum_{n\ge 0}(-1)^nx^n\;,$$

and therefore

\begin{align*} A(x)&=\frac12\sum_{n\ge 0}x^n+\frac32\sum_{n\ge 0}(-1)^nx^n\\\\ &=\sum_{n\ge 0}\left(\frac{1+3(-1)^n}2\right)x^n\;. \end{align*}

You can easily check that

$$\frac{1+3(-1)^n}2=\begin{cases} 2,&\text{if }n\text{ is even}\\ -1,&\text{if }n\text{ is odd}\;. \end{cases}$$