How to Solve Non-Homogeneous Recurrence Relations : $r_n = 2\left(r_{n-1} - \binom{n-1}{2}\right) + \binom{n-1}{2}$? $$r_n = 2\left(r_{n-1} - \binom{n-1}{2}\right) + \binom{n-1}{2}$$
which is equal to $$r_n - 2r_{n-1} = -\frac{n^2-3n+2}{2}$$
This given recurrence relation is derived from the question "How many regions line n could make at most in Euclidean plane?"
To solve this relation and make it into non-recurrent form, 
I had looked in Wikipedia but I only get to the point of solving the homogeneous part only.
$r_n - 2r_{n-1} = 0$ gives $\alpha \cdot2^n$ as a solution of homogenous part.
How should one deal with non-homogeneous part?
 A: Using generating functions
$$f(x)=\sum\limits_{n=0}^{\infty}r_nx^n=r_0+r_1x+r_2x^2+\sum\limits_{n=3}^{\infty}r_nx^n=r_0+r_1x+r_2x^2+\sum\limits_{n=3}^{\infty}\left(2r_{n-1}-\binom{n-1}{2}\right)x^n=\\
r_0+r_1x+r_2x^2+2\left(\sum\limits_{n=3}^{\infty}r_{n-1}x^n\right)-\sum\limits_{n=3}^{\infty}\binom{n-1}{2}x^n=\\
r_0+r_1x+r_2x^2+2x\left(\sum\limits_{n=3}^{\infty}r_{n-1}x^{n-1}\right)-x^3\left(\sum\limits_{n=3}^{\infty}\binom{n-1}{2}x^{n-3}\right)=\\
r_0+r_1x+r_2x^2+2x\left(\sum\limits_{n=2}^{\infty}r_{n}x^{n}\right)-x^3\left(\sum\limits_{n=0}^{\infty}\binom{n+2}{2}x^{n}\right)=...$$
which is, according to this
$$...=r_0+r_1x+r_2x^2+2x\left(f(x)-r_0-r_1x\right)-\frac{x^3}{(1-x)^3}$$
or 
$$f(x)=r_0+r_1x+r_2x^2+2xf(x)-2xr_0-2r_1x^2-\frac{x^3}{(1-x)^3}$$
$$f(x)(1-2x)=r_0(1-2x)+r_1x(1-2x)+r_2x^2-\frac{x^3}{(1-x)^3}$$
$$f(x)=r_0+r_1x+\frac{r_2x^2}{1-2x}-\frac{x^3}{(1-x)^3(1-2x)}$$
$$f(x)=r_0+r_1x+\frac{r_2x^2}{1-2x}-\left(\frac{1}{1-2x}-\frac{1}{1-x}+\frac{1}{(1-x)^2}-\frac{1}{(1-x)^3}\right)$$
$$f(x)=r_0+r_1x+r_2x^2\left(\sum\limits_{n=0}^{\infty}(2x)^{n}\right)-\left(\sum\limits_{n=0}^{\infty}(2x)^n\right)+\left(\sum\limits_{n=0}^{\infty}x^n\right)-\left(\sum\limits_{n=0}^{\infty}(n+1)x^n\right)+\left(\sum\limits_{n=0}^{\infty}\binom{n+2}{2}x^{n}\right)$$
Now, by comparing powers of $x$ we have
$$r_0=r_0$$
$$r_1=r_1-2+1-2+\binom{3}{2}=r_1$$
$$r_2=r_2-4+1-3+\binom{4}{2}=r_2$$
$$r_3=2r_2-8+1-4+\binom{5}{2}=2r_2-1$$
$$...$$
$$r_n=2^{n-2}r_2-2^n+1-(n+1)+\binom{n+2}{2}$$
Or
$$r_n=2^{n-2}r_2+\binom{n+2}{2}-2^n-n$$
Note I had to consider arbitrary $r_0, r_1, r_2$, especially $r_2$, to avoid troubles with $\binom{n-1}{2}$, which makes sense for $n\geq 3$.
A: By induction easy to prove that
$$r_n=r_12^{n-1}+2^n-\frac{n^2+n+2}{2}.$$
Also, you can use the following telescopic sum, but it's very ugly, I think:
$$r_n=2r_{n-1}+\frac{(n-2)(n-1)}{2}$$
$$2^1r_{n-1}=2^2r_{n-2}+2^1\cdot\frac{(n-2)(n-3)}{2}$$
$$2^2r_{n-2}=2^3r_{n-3}+2^2\cdot\frac{(n-3)(n-4)}{2}$$
$$.$$
$$.$$
$$.$$
