<s>[INST] Find the generating function for the recurrence $a_n=a_{n-1}-a_{n-2}$, with $a_0=0$ and $a_1=1.$ This was a test question and I felt confident about it but all he put on it was no and circled a problem and left it at that. My solution up until I messed up which was early was 
$G_a(x) = \sum_{n=0}^\infty a_n x^n$
$G_a(x) = \sum_{n=0}^\infty (a_{n-1}-a_{n-2})x^n$
$G_a(x) = \sum_{n=1}^\infty a_{n-1}x^n+\sum_{n=2}^\infty a_{n-2}x^n + a_0+a_1$
in the second line he circled n=0 in the sum and and then in the third line he wrote n=2 instead of n=1 in the first sum. Can anyone explain and show me how to solve it the correct way.
My final answer was $G_a(x)=\frac{1}{x^2+x-1} $
 [/INST] With as much detail as possible,
$$\begin{align*} G_a(x) &= \sum_{n=0}^\infty a_n x^n \\ &= a_0 x^0 + a_1 x^1 + \sum_{n=2}^\infty a_n x^n \\ &= a_0 + a_1 x + \sum_{n=2}^\infty (a_{n-1} - a_{n-2}) x^n \\ &= a_0 + a_1 x + \sum_{n=2}^\infty a_{n-1} x^n - \sum_{n=2}^\infty a_{n-2} x^n \\ &= a_0 + a_1 x + \sum_{n=1}^\infty a_n x^{n+1} - \sum_{n=0}^\infty a_n x^{n+2} \\ &= a_0 + a_1 x + x \sum_{n=1}^\infty a_n x^n - x^2 \sum_{n=0}^\infty a_n x^n \\ &= a_0 + a_1 x + x \left( -a_0 + \sum_{n=0}^\infty a_n x^n \right) - x^2 G_a(x) \\ &= a_0 + a_1 x + x(-a_0 + G_a(x)) - x^2 G_a(x) \\ &= a_0 + (a_1 - a_0)x + (x - x^2)G_a(x). \end{align*}$$  Therefore, $$G_a(x) = \frac{a_0 + (a_1 - a_0)x}{1 - x + x^2}.$$
</s>