Ordinary generating functions

Question

Let's define the sequence $a_n$, $n \geq 0$ by making $a_0 = 0$ and $a_{n+1} = 2a_n + n$ for $n \geq 0$. Show that if $F(x) = \sum_{n=0}^{\infty} a_nx^n$ is the generating function of the sequence, then $$F(x) = \frac{x^2}{(1-x)^2(1-2x)}$$

Answer 1

$F(x) = \displaystyle{\sum_{n=1}^\infty a_n x^n} = \displaystyle{\sum_{n=1}^\infty (2a_n + n) x^n} = 2\displaystyle{\sum_{n=1}^\infty a_n x^n} + \displaystyle{\sum_{n=1}^\infty n x^n} = 2xF(x) + \displaystyle{\sum_{n=1}^\infty n x^n}$

Now, we know that $\dfrac{1}{1-x} = \displaystyle{\sum_{n=0}^\infty x^n}$, for $|x|<1$. Deriving in both sides, $\dfrac{1}{(1-x)^2} = \displaystyle{\sum_{n=1}^\infty n x^{n-1}}$. Multiplying by $x$ in both sides, $\dfrac{x}{(1-x)^2} = \displaystyle{\sum_{n=1}^\infty n x^n}$.

Therefore:

$$F(x) = 2xF(x) + \dfrac{x}{(1-x)^2}$$

$$F(x) = \frac{x^2}{(1-x)^2(1-2x)}$$

Answer 2

Multiply your recurrence by $x^n$, sum over $n \ge 0$, and recognize: \begin{align} \sum_{n \ge 0} a_{n + 1} x^n &= \frac{F(x) - a_0}{x} \\ \sum_{n \ge 0} n x^n &= x \frac{\mathrm{d}}{\mathrm{d} x} \frac{1}{1 - x} \\ &= \frac{x}{(1 - x)^2} \end{align} to get: $$ \frac{F(x)}{x} = 2 F(x) + \frac{x}{(1 - x)^2} $$ This results in: $$ F(x) = \frac{x^2}{1 - 4 x + 5 x^2 - 2 x^3} = \frac{x^2}{(1 - x)^2 (1 - 2 x)} = \frac{1}{1 - 2x} - \frac{1}{(1 - x)^2} $$ Expanding by the generalized binomial theorem gives: $$ a_n = 2^n - n - 1 $$