Question

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

Short answer

The solution to the recurrence relation is:

$a_k=\frac{38}{9}·2^k+\frac{2}{3}·(k+1)·2^k-\frac{8}{9}{(-1)}^k$

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:

localid="1668594488558" $\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:

localid="1668594464892" ${\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

We have: $a_k=a_{k-1}+2a_{k-2}+2^k{a}_0=4a_1=12$

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 \\ G\left(x\right)-a_0-a_{1}x=\sum _{k=1}^{+\infty }\left(a_{k-1}+2a_{k-2}+2^k\right)x^k{a}_k \\ G\left(x\right)-a_0-a_{1}x=a_{k-1}+2a_{k-2}+2^k \end{gathered}$$

When,

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

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

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

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

Thus the obtained equation is$G\left(x\right)-a_0-a_{1}x=x\left(G\left(x\right)-a_0\right)+2x^{2}G\left(x\right)+\frac{4x^2}{1-2x}$

$$\begin{gathered} G\left(x\right)-a_0-a_{1}x=x\left(G\left(x\right)-a_0\right)+2x^{2}G\left(x\right)+\frac{4x^2}{1-2x} \\ G\left(x\right)-4-12x=x\left(G\right(x)-4)+2x^{2}G\left(x\right)+\frac{4x^2}{1-2x} \\ G\left(x\right)-4-12x=xG\left(x\right)-4x+2x^{2}G\left(x\right)+\frac{4x^2}{1-2x} \\ G\left(x\right)-xG\left(x\right)-2x^{2}G\left(x\right)-4-12x=-4x+\frac{4x^2}{1-2x} \\ G\left(x\right)-xG\left(x\right)-2x^{2}G\left(x\right)=4+8x+\frac{4x^2}{1-2x} \\ \left(1-x-2x^2\right)G\left(x\right)=4+8x+\frac{4x^2}{1-2x} \end{gathered}$$

Divide each side by$1-x-2x^2$;

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

Factorize denominator,

$$\begin{gathered} G\left(x\right)=\frac{(4+8x)(1-2x)+4x^2}{{(1-2x)}^2(x+1)} \\ G\left(x\right)=\frac{4-16x^2+4x^2}{{(1-2x)}^2(x+1)} \\ G\left(x\right)=\frac{4-12x^2}{{(1-2x)}^2(x+1)} \end{gathered}$$

Simplify

Using the partial fractions,

$$\begin{gathered} \frac{4-12x^2}{{(1-2x)}^2(x+1)}=\frac{A}{1-2x}+\frac{B}{{(1-2x)}^2}+\frac{C}{1+x} \\ \frac{4-12x^2}{{(1-2x)}^2(x+1)}=\frac{A(1-2x)(1+x)+B(1+x)+C{(1-2x)}^2}{{(1-2x)}^2(x+1)} \\ \frac{4-12x^2}{{(1-2x)}^2(x+1)}=\frac{A(1-2x)(1+x)+B(1+x)+C\left(1-4x+4x^2\right)}{{(1-2x)}^2(x+1)} \\ \frac{4-12x^2}{{(1-2x)}^2(x+1)}=\frac{A\left(-2x^2-x+1\right)+B(1+x)+C\left(1-4x+4x^2\right)}{{(1-2x)}^2(x+1)} \\ \frac{4-12x^2}{{(1-2x)}^2(x+1)}=\frac{x^2(-2A+4C)+x(-A+B-4C)+(A+B+C)}{{(1-2x)}^2(x+1)} \end{gathered}$$

The numerators have to be identical:

$$\begin{gathered} -2A+4C=-12 \\ -A+B-4C=0 \\ A+B+C=4 \end{gathered}$$

Subtract the second and third equations,

$$\begin{gathered} -2A+4C=-12 \\ -2A-5C=-4 \end{gathered}$$

Subtract the two equations

$$\begin{gathered} 9C=-8 \\ C=-\frac{8}{9} \end{gathered}$$

Determine the other constants;

$$\begin{gathered} A=6-2C \\ =6-\frac{16}{9} \\ =\frac{38}{9} \\ B=4-A-C \\ =4-\frac{38}{9}+\frac{8}{9} \\ =\frac{2}{3} \end{gathered}$$

Thus the obtained equation is:

$G\left(x\right)=\frac{38/9}{1-2x}+\frac{2/3}{{(1-2x)}^2}-\frac{8/9}{1+x}$

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

role="math" localid="1668595806887" $$\begin{gathered} G\left(x\right)=\frac{38}{9}\sum _{k=1}^{+\infty }{\left(2x\right)}^k+\frac{2}{3}\sum _{k=1}^{+\infty }(k+1){\left(2x\right)}^k-\frac{8}{9}\sum _{k=1}^{+\infty }{(-x)}^k \\ G\left(x\right)=\sum _{k=1}^{+\infty }\left(\frac{38}{9}·2^k+\frac{2}{3}·(k+1)·2^k-\frac{8}{9}{(-1)}^k\right)x^k \end{gathered}$$

Therefore., $a_k=\frac{38}{9}·2^k+\frac{2}{3}·(k+1)·2^k-\frac{8}{9}{(-1)}^k$