<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] We can verify a certain periodicity in the terms without solving the recurrence $a_n$. In fact $$a_0=0\\a_1=1\\a_2=1\\a_3=0\\a_4=-1\\a_5=-1\\a_6=0\\a_7=1$$ Hence the sequence of values can be considered as beginning again from $a_6$ and $a_7$; an so on....
Consequently the asked generating function is 
$$\color{red}{F(x)=(x+x^2-x^4-x^5)+(x^7+x^8-x^{10}-x^{11})+(x^{13}+x^{14}-x^{16}-x^{17}) +.....}$$
Considering finitely many terms, in order to get a closed form, we have $$F(x)=(x+x^2-x^4-x^5)(1+x^6+x^{12}+x^{18}+.....+x^{6n})$$
$$F(x)=(x+x^2-x^4-x^5)\left(\frac{x^{6(n+1)}-1}{x^6-1}\right)$$
Finally $$F(x)=(x-x^4)(x+1)\left(\frac{x^{6(n+1)}-1}{x^6-1}\right)=-x(x^3-1)(x+1)\left(\frac{x^{6(n+1)}-1}{x^6-1}\right)=x(x+1)\left(\frac{1-x^{6(n+1)}}{x^3+1}\right)$$
</s>