0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

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.