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

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.

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

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}

• And what about the first part? How do i deal with sums starting from 1 or 2, instead of 0? – leller Feb 14 '19 at 9:12