Question

Use generating functions to solve the recurrence relation ${\mathit{a}}_{\mathbf{k}}\mathbf{=}\mathbf{3}{\mathit{a}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{+}\mathbf{2}$with the initial condition${\mathit{a}}_{\mathbf{0}}\mathbf{=}\mathbf{1}$.

Short answer

The solution to the given recurrence relation is:

$a_k=-1+2·3^k$

Step-by-step solution

Use Generating Function:

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="1668589809758" $$\begin{gathered} \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}} \end{gathered}$$

Extended binomial theorem:

localid="1668589851366" ${\mathbf{(}\mathbf{1}\mathbf{+}\mathbf{x}\mathbf{)}}^{\mathbf{u}}\mathbf{=}\mathbf{\sum }\mathbf{}\mathbf{}_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}\left(\begin{array}{c}u\\ k\end{array}\right){\mathit{x}}^{\mathbf{k}}$

Let

$$\begin{gathered} G\left(x\right)-a_0=\sum _{k=1}^{+\infty }{a}_k{x}^k \\ =\sum _{k=1}^{+\infty }\left(3a_{k-1}+2\right)x^k{a}_k=3a_{k-1}+2\text{when}k\ge 1 \\ =3\sum _{k=1}^{+\infty }{a}_{k-1}{x}^k+2\sum _{k=1}^{+\infty }{x}^k \\ =3x\sum _{k=1}^{+\infty }{a}_{k-1}{x}^{k-1}+2x\sum _{k=1}^{+\infty }{x}^{k-1} \\ =3x\sum _{m=0}^{+\infty }{a}_m{x}^m+2x\sum _{m=0}^{+\infty }{x}^m\text{Let}m=k-1,\sum _{k=1}^{+\infty }{x}^k=\frac{1}{1-x} \\ =3xG\left(x\right)+\frac{2x}{1-x} \end{gathered}$$

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

Calculate the expression for G(x).

$$\begin{gathered} G\left(x\right)-a_0=3xG\left(x\right)+\frac{2x}{1-x}G\left(x\right)-1 \\ =3xG\left(x\right)+\frac{2x}{1-x}G\left(x\right)-3xG\left(x\right)-1 \\ =\frac{2x}{1-x}(1-3x)G\left(x\right)-1 \\ =\frac{2x}{1-x}(1-3x)G\left(x\right) \\ =\frac{2x}{1-x}+1(1-3x)G\left(x\right) \\ =\frac{1+x}{1-x}G\left(x\right) \\ =\frac{1+x}{(1-x)(1-3x)} \end{gathered}$$

determine the partial fractions:

$$\begin{gathered} \frac{1+x}{(1-x)(1-3x)}=\frac{A}{1-x}+\frac{B}{1-3x} \\ =\frac{A(1-3x)+B(1-x)}{(1-x)(1-3x)} \\ =\frac{A-3Ax+B-Bx}{(1-x)(1-3x)} \\ =\frac{(A+B)+(-3A-B)x}{(1-x)(1-3x)} \end{gathered}$$

The numerators have to be identical:

localid="1668590010430" $$\begin{gathered} A+B=1 \\ -3A-B=1 \end{gathered}$$

Add the two equations,

$$\begin{gathered} -2A=2A \\ =-1 \end{gathered}$$

Determine the other constant;

$$\begin{gathered} B=1-A \\ =1-(-1) \\ =1+1 \\ =2 \end{gathered}$$

Thus, we then obtain:

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

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

$$\begin{gathered} G\left(x\right)=-\sum _{k=1}^{+\infty }{x}^k+2\sum _{k=1}^{+\infty }{\left(3x\right)}^k \\ =-\sum _{k=1}^{+\infty }{x}^k+2\sum _{k=1}^{+\infty }{\left(3x\right)}^k \\ =\sum _{k=1}^{+\infty }\left(-1+2·3^k\right)x^k \end{gathered}$$

Thus,$a_k=-1+2·3^k$