I am trying to solve the following problem from Cohen's Basic Techniques of Combinatorial Theory:
A collection of $n$ lines in the plane are are said to be in general position if no two are parallel and no three are concurrent. Let $a_n$ be the number of regions into which $n$ lines in general position divide the plane. How big is $a_n$?
The recurrence relationship for $a_n$ is immediate, namely
$$a_{n+1}=a_n+n.$$
I have been trying to apply generating functions to solve this recurrence, but I am making a mistake somewhere. My attempt is as follows:
Let $G(X)=\sum_{k\geq 1} a_k X^k$. Multiplying both sides of the recurrence by $X^k$ and summing over all valid $k$ gives
$$\sum_{k\geq 1}a_{k+1}X^k=\sum_{k\geq 1}a_kX^k+\sum_{k\geq 1}kX^k.$$
Using the fact that $\frac{1}{(1-x)^2}=\sum_{k\geq 1} kX^k$, I get
$$\sum_{k\geq 1}a_{k+1}X^k=G(X)+\frac{1}{(1-x)^2}.$$
The left hand side is equal to
$$\frac{G(X)-a_1}{X}=\frac{G(X)-2}{X}$$
since $a_1=2$. Solving for $G(X)$, I get
$$G(X)=\frac{2-4X+3x^2}{(1-x)^3}.$$
Expanding with partial fractions gives
$$G(X)=\frac{3}{1-x}-\frac{2}{(1-x)^2}+\frac{1}{(1-x)^3}.$$
Transforming this into power series gives
\begin{align} G(X)&=3\sum_{k\geq 0}X^k-2\sum_{k\geq 0} (k+1)X^k+\sum_{k\geq 0}(k+1)(k+2)X^k\\ &=\sum_{k\geq 0} (3-2(k+1)+(k+1)(k+2))X^k, \end{align} which is not correct. I have tried starting over, but I seems to be making a pretty serious mistake. Any thoughts?
Solution:
The real recurrence relation is $a_{n+1}=a_n+(n+1)$. Let $G(X)=\sum_{k\geq 1} a_k X^k$. Multiplying both sides of the recurrence by $X^k$ and summing over all valid $k$ gives
$$\sum_{k\geq 1}a_{k+1}X^k=\sum_{k\geq 1}a_kX^k+\sum_{k\geq 1}(k+1)X^k.$$
Solving in terms of $G(X)$ gives
$$G(X)=\frac{x(2-2x+x^2)}{(1-x)^3}.$$
By expanding with partial fractions we see
$$G(X)=\frac{x(2-2x+x^2)}{(1-x)^3}=\frac{x}{1-x}+\frac{x}{(1-x)^3}.$$
Using the power series identities $\frac{1}{2}\sum_{k\geq 1}k(k-1)X^{k-1}=\frac{x}{(1-x)^3}$ and $\sum_{k\geq 1}X^k=\frac{x}{1-x}$. Substituting these power series in gives
\begin{align} G(X)&=\frac{1}{2}\sum_{k\geq 1}k(k-1)X^{k-1}+\sum_{k\geq 1}X^k\\ &=\frac{1}{2}\sum_{k\geq 1}k(k+1)X^{k}+\sum_{k\geq 1}X^k \quad \dagger\\ &=\sum_{n\geq 1} (\binom{k+1}{2}+1)X^k. \end{align}
Therefore, by equating coefficients, we have $$a_n=\binom{n+1}{2}+1.$$
The step $\dagger$ follows from the fact that the first coefficient in the power series is $0$.
Note: This is NOT homework, I am merely working through exercises during summer vacation. I'm sure there are other ways to approach the problem, but I am trying to practice using generating functions.
Your recurrence is off by $1$: it should be $a_n=a_{n-1}+n$ for $n>0$, and you could make life a little easier by setting $a_0=1$. Then if you set $a_n=0$ for $n<0$, you can write simply $$a_n=a_{n-1}+n+[n=0]\;,$$ where the last term is an Iverson bracket. Now you get
$$\begin{align*} G(x)&=\sum_na_nx^n\\ &=\sum_na_{n-1}x^n+\sum_nnx^n+1\\ &=xG(x)+\frac{x}{(1-x)^2}+1\;, \end{align*}$$
so
$$\begin{align*} G(x)&=\frac{x}{(1-x)^3}+\frac1{1-x}\\ &=\sum_n\binom{n+2}2x^{n+1}+\sum_nx^n\\ &=\sum_n\binom{n+1}2x^n+\sum_nx^n\;, \end{align*}$$
and $$a_n=\binom{n+1}2+1\;.$$
Note that $\sum_kkx^k=\frac{x}{(1-x)^2}$, not $\frac1{(1-x)^2}$.