Recurrence relations and generating functions question Let $A_n$ be the set of different paving of a $2\times n$ using $2\times 1$ or $1 \times 2$ tiles. We'll define $a_n$=$|A_n|$. 
1] Find recurrence relation: I found it -> $a_n=a_{n-1}+a_{n-2}$ with $a_o=1$, $a_1=1$
2] Solve the recurrence relation equation and find closed form. I found: $$a_n={\sqrt5+1 \over 2\sqrt5} \cdot ({1+\sqrt5 \over 2})^n+{\sqrt5-1 \over 2\sqrt5} \cdot ({1-\sqrt5 \over 2})^n$$
3] My problem: Find the generating function of $a_n$ and receive the expression as in [2].
I found the generating function to be: $A(x)={1-x \over 1-x-x^2}$, and I tried paving my way to the expression but didn't manage to do it. I believe the function I found is correct, but I'm not 100% sure.
Thanks in advance for any assistance! 
 A: Write $1-x-x^2 = (1-ax)(1-bx)$ - 
i.e., find its roots.
Then expand
$\frac{1-x}{1-x-x^2}$
into partial fractions as
$\frac{p}{1-ax}+\frac{q}{1-bx}$.
Making this explicit,
if
$\frac{1-x}{(1-ax)(1-bx)}
=\frac{p}{1-ax}+\frac{q}{1-bx}
$,
multiplying by
$(1-ax)(1-bx)$
gives
$1-x = p(1-bx)+q(1-ax)
= p-pbx+q-qax
= (p+q)-x(pb+qa)
$.
Equating the corresponding terms,
$1 = p+q$ and
$1 = pb+qa$.
Solving these gives
 $p$ and $q$ 
in terms of $a$ and $b$.
Finally use
$\frac{u}{1-vx}
= u\sum_{n=0}^{\infty} v^n x^n
$.
This is all standard
generating function manipulation.
Go here to download
the excellent book "generatingfunctionology"
http://www.math.upenn.edu/~wilf/DownldGF.html.
A: If I'm not very mistaken, your function $A(x)$ is incorrect:
For all $n\geq 2$, the equality $a_nx^n=(a_{n-1}+a_{n-2})x^n$ holds and therefore we get that
$$ A(x) - a_0-a_1x = a_2x^2+a_3x^3+\ldots = \sum_{n\geq 2}(a_{n-1}+a_{n-2})x^n\\
= x\sum_{n\geq 2}a_{n-1}x^{n-1} +x^2\sum_{n\geq 2}a_{n-2}x^{n-2}\\
=x(A(x)-a_0) + x^2A(x).$$
Rearranging this formula seems to yield $A(x)(1-x-x^2) = a_0+a_1x-a_0x=1$ and thus $A(x)=\frac{1}{1-x-x^2}$.
Does this, together with the method of the previous answer get you where you want to be?
