Question

Use generating functions to solve the recurrence relation ${\mathit{a}}_{\mathbf{k}}\mathbf{=}\mathbf{4}{\mathit{a}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{-}\mathbf{4}{\mathit{a}}_{\mathbf{k}\mathbf{-}\mathbf{2}}\mathbf{+}{\mathit{k}}^{\mathbf{2}}$with initial conditions ${\mathit{a}}_{\mathbf{0}}\mathbf{=}\mathbf{2}$and ${\mathit{a}}_{\mathbf{1}}\mathbf{=}\mathbf{5}$.

Short answer

$a_k=k^2+8k+3k{2}^{k+1}-9·2^{k+1}+20$

Step-by-step solution

Sequence for infinite series and Extended Binomial theorem

Generating function for the sequence ${\mathit{a}}_{\mathbf{0}}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{a}}_{\mathbf{k}}\mathbf{,}\mathbf{\dots }$ of real numbers is the infinite series:$\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}{\mathit{a}}_{\mathbf{0}}\mathbf{+}{\mathit{a}}_{\mathbf{1}}\mathit{x}\mathbf{+}{\mathit{a}}_{\mathbf{2}}{\mathit{x}}^{\mathbf{2}}\mathbf{+}\mathbf{\dots }\mathbf{+}{\mathit{a}}_{\mathbf{k}}{\mathit{x}}^{\mathbf{k}}\mathbf{+}\mathbf{\dots }\mathbf{=}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}{\mathit{a}}_{\mathbf{k}}{\mathit{x}}^{\mathbf{k}}$

Extended binomial theorem: ${\mathbf{(}\mathbf{1}\mathbf{+}\mathbf{x}\mathbf{)}}^{\mathbf{u}}\mathbf{=}\mathbf{\sum }\mathbf{}\mathbf{}_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}\mathbf{\left(}\begin{array}{c}\mathbf{u}\\ \mathbf{k}\end{array}\mathbf{\right)}{\mathit{x}}^{\mathbf{k}}$

Use Sequence for infinite series and Extended Binomial theorem

$a_k=4a_{k-1}-4a_{k-2}+k^2{a}_0=2a_1=5$

Let $G\left(x\right)=\sum _{k=0}^{+\infty }{a}_k{x}^k$

$$\begin{gathered} G\left(x\right)-a_0-a_{1}x=\sum _{k=2}^{+\infty }{a}_k{x}^k{a}_k=4a_{k-1}-4a_{k-2}+k^2 \\ k\ge 1 \\ G\left(x\right)-a_0-a_{1}x=\sum _{k=1}^{+\infty }\left(4a_{k-1}-4a_{k-2}+k^2\right)x^k \\ G\left(x\right)-a_0-a_{1}x=4\sum _{k=2}^{+\infty }{a}_{k-1}{x}^k-4\sum _{k=2}^{+\infty }{a}_{k-2}{x}^k+\sum _{k=2}^{+\infty }{k}^2{x}^k \\ G\left(x\right)-a_0-a_{1}x=4x\sum _{k=2}^{+\infty }{a}_{k-1}{x}^{k-1}-4x^2\sum _{k=2}^{+\infty }{a}_{k-2}{x}^{k-2}+x^2\sum _{k=2}^{+\infty }{k}^2{x}^{k-2} \end{gathered}$$

Let $m=k-1$and $n=k-2$

$$\begin{gathered} \sum _{n=0}^{+\infty }\left(\begin{array}{c}p+n-1\\ n\\ \end{array}\right)x^n=\frac{1}{{(1-x)}^p}=4x\left(G\left(x\right)-a_0\right)-4x^{2}G\left(x\right)+\frac{2x^2}{{(1-x)}^3}+\frac{x^2}{{(x-1)}^2}+\frac{x^2}{1-x} \\ \sum _{n=0}^{+\infty }\left(\begin{array}{c}p+n-1\\ n\\ \end{array}\right)x^n==4x\left(G\left(x\right)-a_0\right)-4x^{2}G\left(x\right)+\frac{x^2\left(x^2-3x+4\right)}{{(1-x)}^3} \end{gathered}$$

We thus obtained the equation

$G\left(x\right)-a_0-a_{1}x=4x\left(G\left(x\right)-a_0\right)-4x^{2}G\left(x\right)+\frac{x^2\left(x^2-3x+4\right)}{{(1-x)}^3}$

$$\begin{gathered} G\left(x\right)-a_0-a_{1}x=4x\left(G\left(x\right)-a_0\right)-4x^{2}G\left(x\right)+\frac{x^2\left(x^2-3x+4\right)}{{(1-x)}^3}{a}_0 \\ G\left(x\right)-a_0-a_{1}x=2;a_1=5G\left(x\right)-2-5x=4x \\ \left(G\right(x)-2)-4x^{2}G\left(x\right)+\frac{x^2\left(x^2-3x+4\right)}{{(1-x)}^3} \end{gathered}$$

Distributive property

$G\left(x\right)-2-5x=4xG\left(x\right)-8x-4x^{2}G\left(x\right)+\frac{x^2\left(x^2-3x+4\right)}{{(1-x)}^3}$

Add$-4xG\left(x\right)+4x^{2}G\left(x\right)$to each side

$G\left(x\right)-4xG\left(x\right)+4x^{2}G\left(x\right)-2-5x=-8x+\frac{x^2\left(x^2-3x+4\right)}{{(1-x)}^3}$

Add $2+5x$ to each side

$G\left(x\right)-4xG\left(x\right)+4x^{2}G\left(x\right)=2-3x+\frac{x^2\left(x^2-3x+4\right)}{{(1-x)}^3}$

Factor out$G\left(x\right)$

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

Divide each side by $\left(1-4x+4x^2\right)$

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

Factorize denominator

$$\begin{gathered} G\left(x\right)\frac{2-3x}{{(1-2x)}^2}+\frac{x^2\left(x^2-3x+4\right)}{{(1-x)}^3{(1-2x)}^2} \\ G\left(x\right)=\frac{(2-3x){(1-x)}^3+x^2\left(x^2-3x+4\right)}{{(1-x)}^3{(1-2x)}^2} \\ G\left(x\right)=\frac{4x^4-14x^3+19x^2-9x+2}{{(1-x)}^3{(1-2x)}^2} \end{gathered}$$

Simplify

We found an expression for$G\left(x\right)$, now we need to term the sequence $\left\{a_k\right\}$.

First we will determine the partial fractions

$\frac{4x^4-14x^3+19x^2-9x+2}{{(1-x)}^3{(1-2x)}^2}=\frac{A}{1-x}+\frac{B}{{(1-x)}^2}+\frac{C}{{(1-x)}^3}+\frac{D}{1-2x}+\frac{E}{{(1-2x)}^2}$

We will determine the values of the constants using technology (advised because we need to solve a system of 5 equations with 5 variables).

$$\begin{gathered} A=13 \\ B=5 \\ C=2 \\ D=-24 \\ E=6 \end{gathered}$$

Thus we then obtain:

$G\left(x\right)=\frac{13}{1-x}+\frac{5}{{(1-x)}^2}+\frac{2}{{(1-x)}^3}+\frac{-24}{1-2x}+\frac{6}{{(1-2x)}^2}$

Using$\sum _{k=1}^{+\infty }{x}^k=\frac{1}{1-x}$and

$$\begin{gathered} \sum _{n=0}^{+\infty }\left(\begin{array}{c}p+n-1\\ n\\ \end{array}\right)x^n=\frac{1}{{(1-x)}^p}G\left(x\right) \\ \sum _{n=0}^{+\infty }\left(\begin{array}{c}p+n-1\\ n\\ \end{array}\right)x^n=13\sum _{k=1}^{+\infty }{x}^k+5\sum _{k=1}^{+\infty }(k+1)x^k+2\sum _{k=1}^{+\infty }\left(\begin{array}{c}3+k-1\\ k\\ \end{array}\right)x^k-24\sum _{k=1}^{+\infty }{\left(2x\right)}^k+6\sum _{k=1}^{+\infty }(k+1){\left(2x\right)}^k \\ \sum _{n=0}^{+\infty }\left(\begin{array}{c}p+n-1\\ n\\ \end{array}\right)x^n=\sum _{k=1}^{+\infty }\left(13+5(k+1)+2\left(\begin{array}{c}2+k\\ k\\ \end{array}\right)-24·2^k+6(k+1)2^k\right)x^k \\ \sum _{n=0}^{+\infty }\left(\begin{array}{c}p+n-1\\ n\\ \end{array}\right)x^n=\sum _{k=1}^{+\infty }\left(k^2+8k+3k{2}^{k+1}-9·2^{k+1}+20\right)x^k \end{gathered}$$

We then note$a_k=k^2+8k+3k{2}^{k+1}-9·2^{k+1}+20$

$a_k=k^2+12k+40+2^{k-1}(45k-88)$which is not the same (but similar) to the result in the back of the book, but their might be a calculation error in solution.