Find the generating function for the recurrence $a_n=a_{n-1}-a_{n-2}$, with $a_0=0$ and $a_1=1.$

Question

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} $

Answer 1

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)$$

Answer 2

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}.$$

Answer 3

As an alternative solution :
Given the definition of a generating function:
$A(z)=a_{0}+a_{1}\cdot z+a_{2}\cdot z^{2}\ldots={\displaystyle \sum_{n=0}^{\infty}a_{n}\cdot z^{n}}$
$a_{-n}=0|n>0$
Your problem, as a constraint, is $a_{n}-a_{n-1}+a_{n-2}=0$
$\left(z^{2}-z+1\right)A(z)=a_{0}+a_{1}\cdot z=0+1\cdot z$
Which means that all three term sums are zero starting from the first three.
This leaves two “initial conditions”/starters undefined as: $a_{0},a_{1}$
And the solution is:
$A(z)=\frac{z}{\left(z^{2}-z+1\right)}$
So you had a sign mistake. Unless these problems are done in a simple transparent manner it is hard to spot that type of thing.