Recurrence relations and generating functions question

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!

Answer 1

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?

Answer 2

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.