# finding formula for generating function for recurrence relation

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

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?

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

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