Generating function as Rational Function Find the generating function for the sequence ${a_n}$ defined by:
$$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1$$
for $n\leq 2$ and $a_0=a_1=1$.  Write your answer as a rational function.
 A: To find the generating function, write the recurrence as
$$a_n-4 a_{n-1}+4 a_{n-2}=n(n-1)2^{n-1}+1$$
Multiply both sides by $x^n$ and sun from $n=2$ on:
$$\sum_{n=2}^{\infty} (a_n-4 a_{n-1}+4 a_{n-2}) x^n = \sum_{n=2}^{\infty} n(n-1)2^{n-1} x^n + \sum_{n=2}^{\infty} x^n$$
Define the generating function as 
$$g(x) = \sum_{n=0}^{\infty} a_n x^n$$
We can manipulate the left hand side to produce $g$:
$$\sum_{n=0}^{\infty} a_n x^n - (a_0-a_1x ) - 4 x \left (\sum_{n=0}^{\infty} a_n x^n - a_0\right ) + 4 x^2 \sum_{n=0}^{\infty} a_n x^n \\= (1-4 x+4 x^2)g(x) - (1+x) + 4 x$$
On the RHS, we note that
$$\begin{align}\sum_{n=2}^{\infty} n(n-1)2^{n-1} x^n &= \frac{x^2}{2}\sum_{n=2}^{\infty} n(n-1)2^n x^{n-2} \\ &= \frac{x^2}{2} \frac{d^2}{dx^2} \frac{1}{1-2 x}\end{align}$$
Also
$$\sum_{n=2}^{\infty} x^n = \frac{1}{1-x}-(1+x)$$
Putting this all together:
$$(1-4 x+4 x^2)g(x) - (1+x) + 4 x = \frac{4 x^2}{(1-2 x)^3} + \frac{1}{1-x} - (1+x)$$
With some algebra, we get the rational function sought:
$$g(x) = \frac{1-10 x+44 x^2-84 x^3+80 x^4-32 x^5}{(1-x)(1-2 x)^3 (1-4 x+4 x^2)}$$
The first several terms in the series expansion for this function are
$$g(x) = 1+x+5 x^2+41 x^3+241 x^4+1121 x^5+4481 x^6+16129
   x^7+53761 x^8+168961 x^9+506881
   x^{10}+O\left(x^{11}\right)$$
I leave it to the reader to compare the coefficients to the terms generated in the original recurrence.
