Closed form of a recurrence relation using generating functions It's been awhile since I have done this. The sequence is $\displaystyle a_n = a_{n-1} + 5~a_{n-2}$ with $a_{0}=0$ and $a_{1}=1$. 
I found the generating function to be $\displaystyle G(x) = \frac{x}{(1-x-5x^2)}$ but I am lost on where to go from here. 
 A: Factor the denominator. Slightly unpleasant, since the roots are not rational, but doable. Then use partial fractions to express the generating function in the form $\frac{A}{1-ax}+\frac{B}{1-bx}$. 
It is easy to write down the power series for $\frac{1}{1-ax}$ and $\frac{1}{1-bx}$, by using the fact that $\frac{1}{1-t}=1+t+t^2+t^3+\cdots$.
Then you can get an explicit expression for the coefficient of $x^n$ in each of the terms, and hence in the sum.  
If you run into trouble, I can give more detail. I got the following partial fractions representation:
$$\frac{1}{\sqrt{21}}\left(\frac{1}{1-\frac{1}{2}(1+\sqrt{21})x}-\frac{1}{1-\frac{1}{2}(1-\sqrt{21})x}                             \right) .$$
Remark: There are (to me) easier ways for this particular problem than the generating functions approach. Characteristic equations, though they involve roughly similar manipulations, feel easier.
A: The Characteristic equation of the Recurrence relation is $r^2-r-5=0$
So, $a_n=A\cdot r_1^n+B\cdot r_2^n$ where $r-1,r_2$ are the roots of the above Quadratic Equation
So, $r_1,r_2$ are $\frac{1\pm\sqrt{1^2-4\cdot1(-5)}}{2\cdot1}=\frac{1\pm\sqrt{21}}2$
$0=a_0=A+B\implies B=-A\implies a_n=A(r_1^n-r_2^n)$
$1=a_1=A(r_1-r_2)\implies A=\frac1{(r_1-r_2)}=\sqrt{21}$
$\implies a_n=\sqrt{21}\left(\left(\frac{1+\sqrt{21}}2\right)^n-\left(\frac{1-\sqrt{21}}2\right)^n\right)$
A: Linear algebra also gives an answer: writing the recurrence as 
$\begin{pmatrix}a_n \\ a_{n-1}\end{pmatrix}=\begin{pmatrix}1 & 5 \\ 1 & 0\end{pmatrix}\begin{pmatrix}a_{n-1} \\ a_{n-2}\end{pmatrix}$, 
and using spectral decomposition to find powers of the matrix. Note, that the characteristic polynomial of the matrix equals 
$\rho(\lambda)=\lambda^2-\lambda -5$.
A: Use generating functions, e.g. start defining $A(z) = \sum_{n \ge 0} a_n z^n$. Write the recurrence without subtractions in indices:
$$
a_{n + 2} = a_{n + 1} + 5 a_n
$$
Multiply by $z^n$, sum over $n \ge 0$, recognize the resulting sums:
$$
\frac{A(z) - a_0 - a_1 z}{z^2}
  = \frac{A(z) - a_0}{z} + 5 A(z)
$$
Using the initial values:
$$
A(z) = \frac{z}{1 - z - 5 z^2}
$$
