# Ordinary generating functions

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

• Could you tell what you already tried ? – Claude Leibovici Apr 6 '14 at 13:30
• $$\frac{A}{(1-x)^2}+\frac{B}{1-x}+\frac{C}{1-2x} = \frac{x²}{(1-x)^2(1-2x)}$$ – Franklin Apr 6 '14 at 13:54
• So, what are $A,B,C$ ? – Claude Leibovici Apr 6 '14 at 14:08

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

• How did you go from this $$F(x) = 2F(x) + \frac{x}{(1-x)^2}$$ to this $$F(x)= \frac{x²}{(1-x)²(1-2x)}$$ – Franklin Apr 6 '14 at 15:36
• Just isolate $F(x)$ – Imanol Pérez Arribas Apr 6 '14 at 19:15
• I've edited my answer. I've forgotten an $x$. ($F(x) = 2F(x) + \frac{x}{(1-x)^2}$) – Imanol Pérez Arribas Apr 6 '14 at 20:10

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