Answer to Question #273692 in Discrete Mathematics for kool

Question

Use generating functions to solve the recurrence relation an = 7an−1 −

16an−2 + 12an−3 + n4n

, where a0 = −2, a1 = 0, a2 = 5.

Answer 1

generating function:

$a(x)=\sum a_nx^n$

$\displaystyle\sum_{n=3}^{\infin} (a_n -7a_{n−1} +16a_{n−2} - 12a_{n−3})x^n=\displaystyle\sum_{n=3}^{\infin} n4^nx^n$

$\displaystyle\sum_{n=3}^{\infin}a_nx^n=a(x)-a_0-a_1x-a_2x^2=a(x)+2-5x^2$

$\displaystyle\sum_{n=3}^{\infin}7a_{n-1}x^n=7x\displaystyle\sum_{n=3}^{\infin}a_{n-1}x^{n-1}=7x(a(x)-a_0-a_1x)=7x(a(x)+2)$

$\displaystyle\sum_{n=3}^{\infin}16a_{n-2}x^n=16x^2\displaystyle\sum_{n=3}^{\infin}a_{n-2}x^{n-2}=16x^2(a(x)-a_0)=16x^2(a(x)+2)$

$\displaystyle\sum_{n=3}^{\infin}12a_{n-3}x^n=12x^3\displaystyle\sum_{n=3}^{\infin}a_{n-3}x^{n-3}=12x^3a(x)$

$\displaystyle\sum_{n=3}^{\infin} (a_n -7a_{n−1} +16a_{n−2} - 12a_{n−3})x^n=$

$=a(x)+2-5x^2-7x(a(x)+2)+16x^2(a(x)+2)-12x^3a(x)=$

$=a(x)(1-7x+16x^2-12x^3)-14x+25x^2-12x^3+2$

$\displaystyle\sum_{n=3}^{\infin} n4^nx^n=\frac{x}{(1-4x)^2}$

$a(x)=\frac{x}{(1-7x+16x^2-12x^3)(1-4x)^2}+\frac{14x+25x^2-12x^3+2}{1-7x+16x^2-12x^3}$

$a(x)=\frac{6}{2x-1}+\frac{-1}{(2x-1)^2}+\frac{24}{4x-1}+\frac{4}{(4x-1)^2}+\frac{-27}{3x-1}+\frac{325}{2(2x-1)}+\frac{-55}{2(2x-1)^2}+\frac{647}{4x-1}+\frac{110}{(4x-1)^2}+$

$+\frac{-729}{3x-1}$

$a(x)=\frac{337}{2(2x-1)}-\frac{57}{2(2x-1)^2}+\frac{671}{4x-1}+\frac{114}{(4x-1)^2}-\frac{756}{3x-1}$

$a(x)=-\frac{337}{2}\displaystyle\sum_{n=0}^{\infin} 2^nx^n -671\displaystyle\sum_{n=0}^{\infin} 4^nx^n+756\displaystyle\sum_{n=0}^{\infin} 3^nx^n-\frac{57}{2}\displaystyle\sum_{n=0}^{\infin} \begin{pmatrix} n+1 \\ n \end{pmatrix}2^nx^n+$

$+114\displaystyle\sum_{n=0}^{\infin} \begin{pmatrix} n+1 \\ n \end{pmatrix}4^nx^n$

$a_n=-\frac{337}{2}2^n-671\cdot4^n+756\cdot3^n-\frac{57}{2}(n+1)2^n+114(n+1)4^n$