Find the generating function A(x)=∑n=0∞anxnA(x) = \sum_{n=0}^{\infty} a_n x^nA(x)=∑n=0∞anxn for the recurrence an=an−1+an−2a_n = a_{n-1} + a_{n-2}an=an−1+an−2 with a0=1,a1=1a_0 = 1, a_1 = 1a0=1,a1=1.
11−x−x2\frac{1}{1-x-x^2}1−x−x21
1+x1−x−x2\frac{1+x}{1-x-x^2}1−x−x21+x
11+x+x2\frac{1}{1+x+x^2}1+x+x21
x1−x−x2\frac{x}{1-x-x^2}1−x−x2x