0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.