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)$
On
This is a totally non-original working out of the general linear recurrence.
If $a_n =\sum_{k=1}^m c_k a_{n-k} $ for $n \ge m$, find the generating function $\sum_{n=0}^{\infty} a_n x^n $ in terms of $a_{0..m-1}$ and $c_{1..m}$.
(This is undoubtedly a duplicate, but I just wanted to work this out from scratch. The algebra and rearrangements of summations is complicated enough so that, as usual, I am hoping that someone might have a simpler derivation.)
Given the linear recurrence
$a_n =\sum_{k=1}^m c_k a_{n-k} $ for $n \ge m$.
Find the generating function $A(x) =\sum_{n=0}^{\infty} a_n x^n $ in terms of $a_{0..m-1}$ and $c_{1..m}$.
My answer is
$A(x) =\dfrac{\sum_{r=0}^{m-1} x^r(a_r-\sum_{k=1}^{r} c_{k} a_{r-k})}{1-\sum_{k=1}^m c_k x^k} $.
My derivation.
Let $A_j(x) =\sum_{n=0}^{j} a_n x^n $ for $j = 0$ to $m-1$.
$\begin{array}\\ A(x) &=\sum_{n=0}^{\infty} a_n x^n\\ &=\sum_{n=0}^{m-1} a_n x^n+\sum_{n=m}^{\infty} a_n x^n\\ &=A_{m-1}(x)+\sum_{n=m}^{\infty} x^n\sum_{k=1}^m c_k a_{n-k}\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k\sum_{n=m}^{\infty} x^n a_{n-k}\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^k\sum_{n=m}^{\infty} x^{n-k} a_{n-k}\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^k\sum_{n=m-k}^{\infty} x^{n} a_{n}\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^k(\sum_{n=0}^{\infty} x^{n} a_{n}-\sum_{n=0}^{m-k-1} x^{n} a_{n})\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^k(A(x)-A_{m-k-1}(x))\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^kA(x)-\sum_{k=1}^m c_k x^kA_{m-k-1}(x)\\ \end{array} $
so
$\begin{array}\\ D(x) &=A(x)(1-\sum_{k=1}^m c_k x^k)\\ &=A_{m-1}(x)-\sum_{k=1}^m c_k x^kA_{m-k-1}(x)\\ &=A_{m-1}(x)-\sum_{k=0}^{m-1} c_{m-k} x^{m-k}A_{k-1}(x)\\ &=A_{m-1}(x)-\sum_{k=0}^{m-1} c_{m-k} x^{m-k}\sum_{n=0}^{k-1} a_n x^n\\ &=A_{m-1}(x)-\sum_{n=0}^{m-2}\sum_{k=n+1}^{m-1} c_{m-k} x^{m-k} a_n x^n\\ &=A_{m-1}(x)-\sum_{n=0}^{m-2}\sum_{k=n+1}^{m-1} c_{m-k} a_n x^{n+m-k}\\ &=A_{m-1}(x)-\sum_{n=0}^{m-2}\sum_{r=n+m-m+1}^{n+m-n-1} c_{m-n-m+r} a_n x^{r} \qquad r = n+m-k, k = n+m-r\\ &=A_{m-1}(x)-\sum_{n=0}^{m-2}\sum_{r=n+1}^{m-1} c_{r-n} a_n x^{r}\\ &=A_{m-1}(x)-\sum_{r=1}^{m-1}\sum_{n=0}^{r-1} c_{r-n} a_n x^{r}\\ &=\sum_{r=0}^{m-1} a_r x^r-\sum_{r=1}^{m-1}x^r\sum_{n=0}^{r-1} c_{r-n} a_n\\ &=a_0+\sum_{r=1}^{m-1} x^r(a_r-\sum_{n=0}^{r-1} c_{r-n} a_n)\\ &=\sum_{r=0}^{m-1} x^r(a_r-\sum_{n=0}^{r-1} c_{r-n} a_n)\\ &=\sum_{r=0}^{m-1} x^r(a_r-\sum_{n=1}^{r} c_{n} a_{r-n})\\ &=\sum_{r=0}^{m-1} x^r(a_r-\sum_{k=1}^{r} c_{k} a_{r-k})\\ \end{array} $
Therefore
$A(x) =\dfrac{\sum_{r=0}^{m-1} x^r(a_r-\sum_{k=1}^{r} c_{k} a_{r-k})}{1-\sum_{k=1}^m c_k x^k} $.
In this case, $m=2, c_{1, 2}=2, 1, a_{0, 1} = 1, 2 $ so
$\begin{array}\\ A(x) &=\dfrac{\sum_{r=0}^{m-1} x^r(a_r-\sum_{k=1}^{r} c_{k} a_{r-k})}{1-\sum_{k=1}^m c_k x^k}\\ &=\dfrac{(a_0-\sum_{k=1}^{0} c_{k} a_{0-k})+x(a_1-\sum_{k=1}^{1} c_{k} a_{1-k})}{1-2x-x^2}\\ &=\dfrac{(1)+x(2- c_{1} a_{0})}{1-2x-x^2}\\ &=\dfrac{1+x(2- 2\cdot 2)}{1-2x-x^2}\\ &=\dfrac{1-2x}{1-2x-x^2}\\ \end{array} $
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?