Find solution of system of recurrence relations by using generating function

Question

How can I use generating functions to find $\{a_n\}$ and $\{b_n\}$ if

$\left\{ \begin{array}{l} a_n=a_{n-1}+b_{n-1};\\ b_n=n^2a_{n-1}+b_{n-1};\\ a_0=1, b_0=1. \end{array} \right.$

Thank you in advance.

Answer 1

Hint.

Taking

$\left\{ \begin{array}{l} \sum_{n=1}\left(a_nx^n-a_{n-1}x^n-b_{n-1}x^n\right) = 0\\ \sum_{n=1}\left(b_nx^n-n^2a_{n-1}x^n-b_{n-1}x^n\right)=0\\ \end{array} \right.$

and calling

$$ \sum_{n=0}a_nx^n = A(x)\\ \sum_{n=0}b_nx^n = B(x) $$

we have

$$ \cases{A(x)-a_0-xA(x)-xB(x) = 0\\ B(x) - b_0 -\sum_{n=1}n^2a_{n-1}x^n-xB(x) = 0 } ~~~~(*) $$

now regarding

$$ \sum_{n=1}n^2a_{n-1}x^n = x\sum_{n=0}(n^2+2n+1)a_n x^n $$

and

$$ \sum_{n=0}n a_n x^n = x\frac{d}{dx}\left(\sum_{n=0}a_n x^n\right)=x\frac{d}{dx}A(x) $$

and consequently

$$ \sum_{n=1}n^2 a_n x^n = x\frac{d}{dx}(x\frac{d}{dx}A(x))= x\frac{d}{dx}A(x)+x^2 \frac{d^2}{dx^2}A(x) $$ Then, \begin{align*} \sum_{n=1}n^2a_{n-1}x^n &= x(x\frac{d}{dx}A(x)+x^2 \frac{d^2}{dx^2}A(x)+2x\frac{d}{dx}A(x)+A(x))\\ &=x^3\frac{d^2}{dx^2}A(x)+3x^2\frac{d}{dx}A(x) +xA(x)\end{align*}

Finally, we have $$ (*) \Leftrightarrow \cases{A(x)-xA(x)-xB(x)-1= 0\\ B(x)-x^3\frac{d^2}{dx^2}A(x)-3x^2\frac{d}{dx}A(x)-xA(x)-xB(x)-1 = 0 }~~~~(**) $$

With those rules in mind, you can build a DE involving $A(x)$ whose solution will give you the closed form to $A(x)$. With $A(x)$ developed in series, the series coefficients will give you the sought $\{ a_k\}$ sequence.

NOTE

$A(x), B(x)$ are called generating functions for the sequences $\{ a_k\},\{b_k\}$ respectively.

The resulting DE for $A(x)$ is

$$ x^4 A''(x)+3 x^3 A'(x)+(2 x-1) A(x)+1=0 $$

This DE can be solved proposing for $A(x) = \sum_{k=0}a_k x^k$ furnishing the following recurrences

$$ \left\{a_0-1=0,a_1-2 a_0=0,a_2-2 a_1=0,-3 a_1-2 a_2+a_3=0,-8 a_2-2 a_3+a_4=0,-15 a_3-2 a_4+a_5=0,-24 a_4-2 a_5+a_6=0,\cdots,\right\} $$

or $a_0 = 1, a_1 = 2, a_2 = 4$ and for $n\ge 3$

$$ \cases{ a_n = 2a_{n-1}+n(n-2)a_{n-2}\\ b_n = a_{n-1}+n(3n-2) a_{n-2}+n^2(n-1)(n-3)a_{n-3} } $$