Combinatorics - rewriting generating function as power series

Question

I have been working on the following question:

Find a recurrence relation for the number of regions created by $n$ mutually intersecting circles on a piece of paper (no three circles have a common intersecting point). Then, show using the generating function that $$a_n = n^2 - n +2$$ for $n \ge 1$.

I have found $$a_n = a_{n-1} + 2(n-1)$$ with $a_1 = 2$. I have also found that the generating function is $$f(x) = \frac{2x^3-2x^2+2x}{(1-x)^3}.$$ Now, I just have to rewrite it to the power series, but I can't seem to get the right result. Can somebody help me with this?

Thanks in advance!

Answer 1

Applying partial fraction decomposition yields \begin{align} \frac{2x^3-2x^2+2x}{(1-x)^3} &= -2 + \frac{4}{1-x} - \frac{4}{(1-x)^2} + \frac{2}{(1-x)^3} \\ &= -2 + 4\sum_{n \ge 0} x^n - 4 \sum_{n \ge 0} \binom{n+1}{1} x^n + 2 \sum_{n \ge 0} \binom{n+2}{2} x^n \\ &= -2x^0 + \sum_{n \ge 0} \left(4 - 4 \binom{n+1}{1} + 2 \binom{n+2}{2}\right) x^n, \end{align} which immediately implies that \begin{align} a_n &= -2[n=0] + 4 - 4 \binom{n+1}{1} + 2 \binom{n+2}{2} \\ &= -2[n=0]+n^2-n+2 \\ &= \begin{cases} 0 &\text{if $n=0$} \\ n^2-n+2 &\text{if $n>0$} \end{cases} \end{align}

Answer 2

Here is another variation.

We obtain \begin{align*} &\color{blue}{\frac{2x^3-2x^2+2x}{(1-x)^3}}=\sum_{n=0}^{\infty}\binom{-3}{2}(-x)^n\tag{1}\\ &\quad=\left(2x^3-2x^2+2x\right)\sum_{n=0}^{\infty}\binom{n+2}{2}x^n\tag{2}\\ &\quad=\sum_{n=0}^{\infty}(n+1)(n+2)\left(x^{n+3}-x^{n+2}+x^{n+1}\right)\\ &\quad=\sum_{n=3}^{\infty}(n-2)(n-1)x^n-\sum_{n=2}^{\infty}(n-1)nx^n+\sum_{n=1}^{\infty}n(n+1)x^n\tag{3}\\ &\quad=\sum_{n=3}\left((n-2)(n-1)-(n-1)n+n(n+1)\right)x^n\\ &\quad\qquad+\left(2\cdot 3-1\cdot 2\right)x^2+2x\\ &\quad=\sum_{n=3}^{\infty}\left(n^2-n+2\right)x^n+4x^2+2x\\ &\quad\,\,\color{blue}{=\sum_{n=1}^{\infty}\left(n^2-n+2\right)x^n} \end{align*}

Comment:

• In (1) we use the binomial series expansion.

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we multiply out and shift the indices to get terms with $x^n$.