Solve generating function in recurring form

Question

I have a sequence set as:

$a_0 = 1, a_n = \frac{3}{2}a_{n-1} - \frac{n}{2}$ for $ n \ge 1$

I have started with: $$A(x) = \sum_{n=0}^\infty a_nx^n$$ $$ a_n = \frac{3}{2}a_{n-1} - \frac{n}{2} $$ $$ 2a_nx^n = 3a_{n-1}x^n - nx^n$$ $$ 2 \cdot \sum_{n=1}^\infty a_nx^n = 3 \cdot \sum_{n=1}^\infty (a_{n-1}x^n) - \sum_{n=1}^\infty nx^n$$

$$ 2 \cdot \sum_{n=1}^\infty a_nx^n = 3x \cdot A(x) - \sum_{n=1}^\infty nx^n$$

I hope these steps are correct, now I'm not sure about this relation:

$$ 2 \cdot \sum_{n=1}^\infty a_nx^n = 2x \cdot a_0 \cdot \sum_{n=1}^\infty a_{n-1}x^{n-1} = 2x A(x) $$

And I don't know that to do with the $-\sum_{n=1}^\infty nx^n$.

Could you help me with the above?

// EDIT: So now I've got:

$$A(x) = \sum_{n=1}^\infty nx^n $$

Which I'm still not sure what to do with that.

Answer 1

You are correct up until $$ 2 \cdot \sum_{n=1}^\infty a_nx^n = 3x \cdot A(x) - \sum_{n=1}^\infty nx^n $$ You then evaluated the first sum, $\sum_{n=1}^\infty a_nx^n$, incorrectly. You cannot "factor out" $a_0$ the way you did. Instead, since we are summing over $n\ge 1$, the only thing missing the $n=0$ term, so the entire sum is just equal to $A(x)-a_0$. That is, $$ \begin{align} 2 \cdot \sum_{n=1}^\infty a_nx^n &=2(a_1x+a_2x^2+\dots) \\&= 2(\color{blue}{-a_0} + \color{blue}{a_0}+a_1x+a_2x^2+\dots) \\&= 2(-a_0+A(x))\\&= 2(A(x)-1) \end{align} $$ For the last summation, we use the following trick, where we notice that there is a factor of $nx^{n-1}$, which is the derivative of $x^n$, allowing us to write this sum in terms of the derivative of another series. You will get used to this trick after seeing it a lot, even though it can be a bit difficult to learn.

Let $D$ denote the differentation operator. For example, $D[\sin x]=\cos x$ and $D[x^n]=nx^{n-1}$. Then $$ \begin{align} \sum_{n= 1}^\infty nx^{n} &=x\cdot \sum_{n=1}^\infty nx^{n-1} \\&=x\cdot \sum_{n=1}^\infty D[x^n] \\&\stackrel1=x\cdot D\left[\sum_{n=1}^\infty x^n\right] \\&\stackrel2=x\cdot D\left[\frac{x}{1-x}\right] \\&\stackrel3=x\cdot \frac1{(1-x)^2} \end{align} $$ Explanation:

1. The derivative operator is linear, and distributes over infinite sums.

2. Use the infinite geometric series formula to evaluate $\sum_{n=1}^\infty x^n$.

3. Evaluate the derivative using the quotient rule.

Answer 2

We finish off what you started and fill in some details. We first convert the recurrence into a series:

$$ \sum_{n = 1}^{\infty} a_n x^n = \frac{3}{2} \sum_{n = 0}^{\infty} a_n x^{n + 1} - \sum_{n = 1}^{\infty} \frac{n}{2} x^n $$

and get:

$$ A(x) - a_0 = \frac{3}{2} \cdot x \cdot A(x) - \frac{1}{2} \sum_{n = 1}^{\infty} n x^n $$

the last term being:

$$ \sum_{n = 1}^{\infty} nx^n = x \cdot \sum_{n = 1}^{\infty} nx^{n - 1} = x \cdot \frac{d}{dx} \sum_{n = 1}^{\infty} x^n $$ $$ = x \cdot \frac{d}{dx} \left( \frac{1}{1 - x} \right) = \frac{x}{(1 - x)^2} $$

And so we get:

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

After rearranging and with $a_0 = 1$:

$$ A(x) = \frac{2x^2 - 5x + 2}{(1 - x)^2(2 - 3x)} $$

Applying partial fraction decomposition we get:

$$ A(x) = \frac{2}{1 - x} + \frac{1}{(1 - x)^2} - \frac{4}{2 - 3x} $$

Converting the terms above back to series we get:

$$ A(x) = \sum_{n = 0}^{\infty} a_n x^n = \sum_{n = 0}^{\infty} 2 x^n + \sum_{n = 0}^{\infty}(n + 1)x^n - \sum_{n = 0}^{\infty} 2\left(\frac{3}{2} \right)^n x^n $$

And so we conclude:

$$ a_n = n - 2 \left( \frac{3}{2} \right)^n + 3 $$

Which we can verify using induction.