Find generating function of $ a_n=2a_{n-1}-3a_{n-2}+4n-1 $

Question

I have to find generating function of $ a_n=2a_{n-1}-3a_{n-2}+4n-1 $ where $a_0=1$ and $a_1=3$. I'm currently stuck at the form:

$f(x) = \sum_{n=0}^\infty a_nx^n = 1 + 3x +2x\sum_{n=2}^\infty(a_{n-1}x^{n-1})-3x^2\sum_{n=2}^\infty(a_{n-2}x^{n-2})+\sum_{n=2}^\infty((4n-1)x^{n})$

I have no idea how to go further.

Answer 1

Hint.

Calling $A(x)=\sum_{k=0}^{\infty} a_k x^k$ we have

$$ (a_k-2a_{k-1}+3a_{k-2})x^k = (4n-1)x^k $$

and

$$ \sum_{k=2}^{\infty}a_k x^k = A(x) - a_0-a_1 x\\ \sum_{k=2}^{\infty}a_{k-1} x^k = x(A(x)-a_0)\\ \sum_{k=2}^{\infty}a_{k-2} x^k = x^2A(x) $$

and also

$$ \sum_{k=2}^{\infty}k x^k = \frac{1}{(1-x)^2}-1-x\\ \sum_{k=2}^{\infty}x^k = \frac{1}{1-x}-1-x $$

and after some algebraic operations

$$ A(x) = \frac{1}{1-2x+3x^2}\left(\frac{1}{(1-x)^2}-\frac{1}{1-x}-a_0+a_1 x\right) $$

Answer 2

Let's restart from beginning. We have $$ \left\{ \matrix{ a_{\,n} = 0\quad \left| {\;n < 0} \right. \hfill \cr a_{\,0} = 1 \hfill \cr a_{\,1} = 3 \hfill \cr a_{\,n} = 2a_{\,n - 1} - 3a_{\,n - 2} + 4n - 1 \hfill \cr} \right. $$

The best approach is to adjust the recurrence as to accomodate the initial values. We shall do in this way $$ \eqalign{ & a_{\,0} = 1 = 2a_{\,0 - 1} - 3a_{\,0 - 2} + 4 \cdot 0 - 1 = - 1\quad \Rightarrow \cr & \Rightarrow \quad a_{\,n} = 2a_{\,n - 1} - 3a_{\,n - 2} + 4n - 1 + 2\left[ {0 = n} \right] \cr & a_{\,1} = 3 = 2a_{\,0} - 3a_{\,1 - 2} + 4 \cdot 1 - 1 + 2\left[ {0 = 1} \right] = 5\quad \Rightarrow \cr & a_{\,n} = 2a_{\,n - 1} - 3a_{\,n - 2} + 4n - 1 + 2\left[ {0 = n} \right] - 2\left[ {1 = n} \right] \cr} $$ where $[P]$ denotes the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

So we get a recurrence which is valid for all $0 \le n$. $$ \left\{ \matrix{ a_{\,n} = 0\quad \left| {\;n < 0} \right. \hfill \cr a_{\,n} = 2a_{\,n - 1} - 3a_{\,n - 2} + 4n - 1 + 2\left[ {0 = n} \right] - 2\left[ {1 = n} \right] \hfill \cr} \right. $$ or better $$ a_{\,n} = 2\left[ {1 \le n} \right]a_{\,n - 1} - 3\left[ {2 \le n} \right]a_{\,n - 2} + 4n - 1 + 2\left[ {0 = n} \right] - 2\left[ {1 = n} \right]\quad \left| {\;0 \le n} \right. $$

Now we can multiply by $x^n$ and sum $$ \eqalign{ & f(x) = \sum\limits_{n = 0}^\infty {a_{\,n} x^{\,n} } = \cr & = 2\sum\limits_{n = 0}^\infty {\left[ {1 \le n} \right]a_{\,n - 1} x^{\,n} } - 3\sum\limits_{n = 0}^\infty {\left[ {2 \le n} \right]a_{\,n - 2} x^{\,n} } + \cr & + 4\sum\limits_{n = 0}^\infty {nx^{\,n} } - \sum\limits_{n = 0}^\infty {1x^{\,n} } + 2\sum\limits_{n = 0}^\infty {\left[ {0 = n} \right]x^{\,n} } - 2\sum\limits_{n = 0}^\infty {\left[ {1 = n} \right]x^{\,n} } = \cr & = 2\sum\limits_{n = 1}^\infty {a_{\,n - 1} x^{\,n} } - 3\sum\limits_{n = 2}^\infty {a_{\,n - 2} x^{\,n} } + \cr & + 4\sum\limits_{n = 0}^\infty {nx^{\,n} } - \sum\limits_{n = 0}^\infty {1x^{\,n} } + 2x^{\,0} - 2x^{\,1} = \cr & = 2\sum\limits_{n = 0}^\infty {a_{\,n} x^{\,n + 1} } - 3\sum\limits_{n = 0}^\infty {a_{\,n} x^{\,n + 2} } + 4\sum\limits_{n = 0}^\infty {nx^{\,n} } - \sum\limits_{n = 0}^\infty {x^{\,n} } + 2 - 2x = \cr & = \left( {2x - 3x^{\,2} } \right)\sum\limits_{n = 0}^\infty {a_{\,n} x^{\,n} } + 4\sum\limits_{n = 0}^\infty {nx^{\,n} } - {1 \over {1 - x}} + 2 - 2x \cr} $$

And the term with $nx^n$ becomes $$ \eqalign{ & \sum\limits_{n = 0}^\infty {nx^{\,n} } = \sum\limits_{n = 1}^\infty {nx^{\,n} } = x\sum\limits_{n = 1}^\infty {nx^{\,n - 1} } = \cr & = x{d \over {dx}}\sum\limits_{n = 0}^\infty {x^{\,n} } = {x \over {\left( {1 - x} \right)^{\,2} }} \cr} $$

Finally $$ \eqalign{ & f(x) = \left( {2x - 3x^{\,2} } \right)f(x) + 4{x \over {\left( {1 - x} \right)^{\,2} }} - {1 \over {1 - x}} + 2 - 2x \cr & f(x) = {{5x - 1} \over {\left( {1 - 2x + 3x^{\,2} } \right)\left( {1 - x} \right)^{\,2} }} + {{\left( {1 - x} \right)} \over {\left( {1 - 2x + 3x^{\,2} } \right)}} \cr} $$