Question

Use generating functions to solve the recurrence relation ${\mathit{a}}_{\mathbf{k}}\mathbf{=}\mathbf{2}{\mathit{a}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{+}\mathbf{3}{\mathit{a}}_{\mathbf{k}\mathbf{-}\mathbf{2}}\mathbf{+}{\mathbf{4}}^{\mathbf{k}}\mathbf{+}\mathbf{6}$with initial conditions.$a_0=20,a_1=60$

Short answer

$a_k=-\frac{3}{2}+\frac{16}{5}·4^k+\frac{67}{4}·3^k+\frac{31}{20}·{(-1)}^k$

Step-by-step solution

Step 1: 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:

localid="1668610118668" ${(1+x)}^u=\sum _{k=0}^{+\infty }\left(k\right)x^k$

Step 2: Use Sequence for infinite series and Extended Binomial theorem

Equation is:

Let

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

$G\left(x\right)-a_0-a_{1}x=\sum _{k=1}^{+\infty }\left(2a_{k-1}+3a_{k-2}+4^k+6\right)x^k$

$G\left(x\right)-a_0-a_{1}x=2\sum _{k=2}^{+\infty }{a}_{k-1}{x}^k+3\sum _{k=2}^{+\infty }{a}_{k-2}{x}^k+\sum _{k=2}^{+\infty }{4}^k{x}^k+6\sum _{k=2}^{+\infty }{x}^k$

$G\left(x\right)-a_0-a_{1}x=2x\sum _{k=2}^{+\infty }{a}_{k-1}{x}^{k-1}+3x^2\sum _{k=2}^{+\infty }{a}_{k-2}{x}^{k-2}+16x^2\sum _{k=2}^{+\infty }{4}^{k-2}{x}^{k-2}+6a$

Whenlocalid="1668588629789" $k⩾2$:

We thus obtained the equation

$G\left(x\right)-a_0-a_{1}x=2x\sum _{m=1}^{+\infty }{a}_m{x}^m+3x^2\sum _{n=0}^{+\infty }{a}_n{x}^n+16x^2\sum _{n=0}^{+\infty }{4}^n{x}^n+6x^2\sum _{n=0}^{+\infty }{x}^n$

$G\left(x\right)-a_0-a_{1}x=2x\left(G\left(x\right)-a_0\right)+3x^{2}G\left(x\right)+16x^2\sum _{n=0}^{+\infty }{\left(4x\right)}^n+\frac{6x^2}{1-x}$

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

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

$\sum _{n=0}^{+\infty }{x}^n=\frac{1}{1-x}{x}^n=\frac{1}{1-x}$

We thus obtained the equation

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

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

$a_0=20;a_1=60$

Distributive property

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

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

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

Add to each side.

G(x) &=\frac{20+20 x}{\left(1-2 x-3 x^{2}\right)}+\frac{22 x^{2}-40 x^{3}}{(1-x)(1-4 x)\left(1-2 x-3 x^{2}\right)} \text { Factor out } G(x) \\

G(x) &=\frac{20+20 x}{(1-3 x)(1+x)}+\frac{22 x^{2}-40 x^{3}}{(1-x)(1-4 x)(1-3 x)(1+x)} \text Divide each side by

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

We found an expression for , now we need to term the sequence .

First we will determine the partial fractions

$\frac{40x^3+2x^2-80x+20}{(1-x)(1-4x)(1-3x)(1+x)}=\frac{A}{1-x}+\frac{B}{1-4x}+\frac{C}{1-3x}+\frac{D}{1+x}$

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

$A=-\frac{3}{2}$

$B=\frac{16}{5}$

$C=\frac{67}{4}$

$D=\frac{31}{20}$

Thus we then obtain:$G\left(x\right)=\frac{-3/2}{1-x}+\frac{16/5}{1-4x}+\frac{67/4}{1-3x}+\frac{31/20}{1+x}$

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

$G\left(x\right)=-\frac{3}{2}\sum _{k=1}^{+\infty }{x}^k+\frac{16}{5}\sum _{k=1}^{+\infty }{\left(4x\right)}^k+\frac{67}{4}\sum _{k=1}^{+\infty }{\left(3x\right)}^k+\frac{31}{20}\sum _{k=1}^{+\infty }{(-x)}^k$

$G\left(x\right)=\sum _{k=1}^{+\infty }\left(-\frac{3}{2}+\frac{16}{5}·4^k+\frac{67}{4}·3^k+\frac{31}{20}·{(-1)}^k\right)x^k$

We then note .$a_k=-\frac{3}{2}+\frac{16}{5}·4^k+\frac{67}{4}·3^k+\frac{31}{20}·(-1{)}^k$