Answer to Question #218197 in Discrete Mathematics for Ahmad

Question

Find the generating function of recurrence relation an+1_an=3n ,n less than 0 where ao=1

Answer 1

We have the recurrence relation $a_{n+1}-a_n=3n$, for n less than 0, where $a_0=1$.

Let's consider the sequence $b_m=a_{-m}$, $m=-n$, such that $m\in\mathbb{N}\cup\{0\}$. Then

$a_{n+1}-a_n=a_{-m+1}-a_{-m}=b_{m-1}-b_m=3n=-3m$, or $b_m-b_{m-1}=3m$.

$b_m=(b_m-b_{m-1})+(b_{m-1}-b_{m-2})+\dots+(b_1-b_0)+b_0$

$=3m+3(m-1)+\dots+3+b_0=\frac{3}{2}m(m+1)+1$

The generating function of the sequence $a_n$ is

$f(z)=\sum\limits_{n=-\infty}^0a_nz^n=\sum\limits_{m=0}^{+\infty}b_mz^{-m}=$

$\sum\limits_{m=0}^{+\infty}\left(\frac{3}{2}m(m+1)+1\right)z^{-m}=\sum\limits_{m=0}^{+\infty}z^{-m}+\frac{3}{2}\sum\limits_{m=0}^{+\infty}m(m+1)z^{-m}$

$=\frac{1}{1-z^{-1}}+\frac{3}{2}z^2\frac{d^2}{dz^2}\sum\limits_{m=0}^{+\infty}z^{-m}=\frac{1}{1-z^{-1}}+\frac{3}{2}z^2\frac{d^2}{dz^2}\frac{1}{1-z^{-1}}$

$=\frac{1}{1-z^{-1}}+3\frac{z^2}{(z-1)^3}=\frac{1}{1-z^{-1}}+\frac{3z^{-1}}{(1-z^{-1})^3}$

Answer. The generating function of the sequence $a_n$ is $f(z)=\frac{1}{1-z^{-1}}+\frac{3z^{-1}}{(1-z^{-1})^3}$.