2. Use generating functions to solve the recurrence relation an = 4an−1 − 4an−2 + n2, where a0 = 2, a1 = 5.

$a_n-4a_{n-1}+4a_{n-2}=n^2$

$\displaystyle\sum_{n=2}^{\infin}a_nx^n-4\displaystyle\sum_{n=2}^{\infin}a_{n-1}x^{n}+4\displaystyle\sum_{n=2}^{\infin}a_{n-2}x^{n}=\displaystyle\sum_{n=2}^nn^2x^n$

From the table

$\displaystyle\sum_{n=0}^nn^2x^n=0+x+2^2x^2+3^2x^3+...=\dfrac{x(x+1)}{(1-x)^3}$

$G(x)-2-5x-4x(G(x)-2)+4x^2G(x)$

$=\dfrac{x(x+1)}{(1-x)^3}-x$

$G(x)(1-4x+4x^2)=\dfrac{x(x+1)}{(1-x)^3}-4x+2$

$G(x)=\dfrac{x^2+x}{(1-x)^3(1-2x)^2}+\dfrac{2}{1-2x}$

$\dfrac{x^2+x}{(1-x)^3(1-2x)^2}=\dfrac{A}{(1-x)^3}+\dfrac{B}{(1-x)^2}+\dfrac{C}{1-x}$

$+\dfrac{D}{(1-2x)^2}+\dfrac{E}{1-2x}$

$A(1-2x)^2+B(1-x)(1-2x)^2$

$+C(1-x)^2(1-2x)^2+D(1-x)^3$

$+E(1-x)^3(1-2x)=\dfrac{x^2+x}{(1-x)^3(1-2x)^2}$

$x=0:A+B+C+D+E=0$

$x=-1:9A+18B+36C+8D+24E=0$

$x=1:A=2$

$x=1/2:D=6$

$x=2:9A-9B+9C-D+3E=6$

$A=2, B=-3, C=-3, D=6, E=-2$

$G(x)=\dfrac{2}{(1-x)^3}-\dfrac{3}{(1-x)^2}-\dfrac{3}{1-x}$

$+\dfrac{6}{(1-2x)^2}-\dfrac{2}{1-2x}+\dfrac{2}{1-2x}$

$\def\arraystretch{1.5} \begin{array}{c:c} \dfrac{2}{(1-x)^3} & 2\dbinom{n+2}{2} \\ \\ -\dfrac{3}{(1-x)^2} & -3(n+1)\\ \\ -\dfrac{3}{1-x} & -3 \\ \\ \dfrac{6}{(1-2x)^2} & 6(n+1)(2^n) \end{array}$

$a_n=2\dbinom{n+2}{2}-3(n+1)-3+6(2^n)(n+1)$