I need to solve the recurrence relation
$$A_n=2A_{n-1}+A_{n-2}$$
with $A(t)=\sum_{n=0}^\infty A_n t^n$ and initial conditions $A_0 = 1$ and $A_1=2$.
I am trying to find the generating function and keep getting the incorrect answer, any tips?
Answer: $A(t)=1/\left(1-2t-t^2\right)$
Best Answer
So your recurrence is valid for all $n \ge 2$ and hence we have $$ \begin{split} \sum_{n=2}^\infty A_n x^n &= A(x) - A_1x - A_0 \\ \sum_{n=2}^\infty A_{n-1} x^n &= x \sum_{n=2}^\infty A_{n-1} x^{n-1} = x \sum_{n=1}^\infty A_m x^m = x(A(x) - A_0) \\ \sum_{n=2}^\infty A_{n-2} x^n &= x^2 \sum_{n=2}^\infty A_{n-2} x^{n-2} = x^2A(x) \end{split} $$ and substituting this into your recurrence, you get $$ A(x) - A_1 x - A_0 = 2x(A(x) - A_0) + x^2A(x) $$ Can you finish?