Lines in the plane and recurrence relation

Solution 1:

As an alternative to generating functions (which is usually a very nice way to solve problems), let me mention the following. Assume no three lines are concurrent.

Each time a line is added, it adds a region for each region it passes through, i.e. it divides that region in two. The number of regions through which a line passes is equal to the number of lines crossed plus one. Each time the line crosses another line, it creates a point of intersection, so we could count the number of lines crossed plus one to be the number of points of intersection added plus the number of lines added. Thus, the number of regions is one (the plane) plus the number of points of intersection plus the number of lines.

If we have $n$ lines, there are $\binom{n}{2}$ points of intersection. Thus, the number of regions is $$ \binom{n}{2}+\binom{n}{1}+\binom{n}{0} $$

Solution 2:

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