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