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{4}}^{\mathbf{k}\mathbf{-}\mathbf{1}}$ with the initial condition${\mathit{a}}_{\mathbf{0}}\mathbf{=}\mathbf{1}$.

Short answer

$a_k=4^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="1668591975072" $\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: $\left|{\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}}\right|$

Use Sequence for infinite series and Extended Binomial theorem

Equation is:

$a_k=3a_{k-1}+4^{k-1}{a}_0=1$

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

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

Where $k\ge 1$

$$\begin{gathered} G\left(x\right)-a_0=3\sum _{k=1}^{+\infty }{a}_{k-1}{x}^k+\sum _{k=1}^{+\infty }{4}^{k-1}{x}^k \\ G\left(x\right)-a_0=3x\sum _{k=1}^{+\infty }{a}_{k-1}{x}^{k-1}+x\sum _{k=1}^{+\infty }{4}^{k-1}{x}^{k-1} \\ G\left(x\right)-a_0=3x\sum _{m=0}^{+\infty }{a}_m{x}^m+x\sum _{m=0}^{+\infty }{\left(4x\right)}^m \end{gathered}$$

Let $m=k-1$

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

Simplify

We thus obtained the equation $G\left(x\right)-a_0=3xG\left(x\right)+\frac{x}{1-4x}$ $$\begin{gathered} G\left(x\right)-a_0=3xG\left(x\right)+\frac{x}{1-4x} \\ G\left(x\right)-1=3xG\left(x\right)+\frac{x}{1-4x} \end{gathered}$$

$a_0=1$. Now subtract$3xG\left(x\right)$

from each side: $G\left(x\right)-3xG\left(x\right)-1=\frac{x}{1-4x}$

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

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

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

Divide each side by $1-3x$: $G\left(x\right)=\frac{1}{(1-4x)}$

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

$G\left(x\right)=\sum _{k=1}^{+\infty }{\left(4x\right)}^k=\sum _{k=1}^{+\infty }{4}^k{x}^k$

We then get $a_k=4^k$