Answer to Question #273393 in Discrete Mathematics for Amitansu

Question

2. Use generating functions to solve the recurrence relation a_n = 4a_n−1 − 4a_n−2 + n², where a₀ = 2, a₁ = 5.

Answer 1

$$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)$$