Question

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

Find the coefficient of ${\mathit{x}}^{\mathbf{5}}{\mathit{y}}^{\mathbf{8}}$in${\mathbf{(}\mathbf{x}\mathbf{+}\mathbf{y}\mathbf{)}}^{\mathbf{13}}$.

Short answer

• $a_k=18·3^k-12·2^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:

$\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.

The given equation is$a_k=5a_{k-1}-6a_{k-2}, a_0=6, a_1=30$

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

$a_k=5a_{k-1}+6a_{k-2}$, when $k\ge 1$

$$\begin{gathered} G\left(x\right)-a_0-a_{1}x=5\sum _{k=2}^{+\infty }{a}_{k-1}{x}^k-6\sum _{k=2}^{+\infty }{a}_{k-2}{x}^k \\ G\left(x\right)-a_0-a_{1}x=5x\sum _{k=2}^{+\infty }{a}_{k-1}{x}^{k-1}-6x^2\sum _{k=2}^{+\infty }{a}_{k-2}{x}^{k-2} \\ G\left(x\right)-a_0-a_{1}x=5x\sum _{m=1}^{+\infty }{a}_m{x}^m-6x^2\sum _{n=0}^{+\infty }{a}_n{x}^n \end{gathered}$$

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

$G\left(x\right)-a_0-a_{1}x=5x\left(G\left(x\right)-a_0\right)-6x^{2}G\left(x\right)$

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

$$\begin{gathered} G\left(x\right)-a_0-a_{1}x=5x\left(G\left(x\right)-a_0\right)-6x^{2}G\left(x\right) \\ G\left(x\right)-6-30x=5x\left(G\right(x)-6)-6x^{2}G\left(x\right) \end{gathered}$$

$a_0=6$and $a_1=30$

localid="1668593092016" $$\begin{gathered} G\left(x\right)-6-30x=5xG\left(x\right)-30x-6x^{2}G\left(x\right) \\ G\left(x\right)-5xG\left(x\right)+6x^{2}G\left(x\right)-6-30x=-30x \end{gathered}$$

G(x)-6-30x=5xG(x)-30x-6x2G(x)G(x)-5xG(x)+6x2G(x)-6-30x=-30x

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

$G\left(x\right)-5xG\left(x\right)+6x^{2}G\left(x\right)=6$

Add $6+30x$to each side.

$\left(1-5x+6x^2\right)G\left(x\right)=6$

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

$\left(1-5x+6x^2\right)G\left(x\right)=6$

Factor out$G\left(x\right)$, and divide each side by$1-5x-6x^2$: $G\left(x\right)=\frac{6}{1-5x+6x^2}$

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

Simplify

We found an expression for$G\left(x\right)$, now we need to terminate the sequence\[\left\{ {{a}_{k}} \right\}\].

First, we will determine the partial fractions;

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

The numerators have to be identical:

$$\begin{gathered} -A-B=6 \\ 2A+3B=0 \end{gathered}$$

Multiply the first equation by 2

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

Add the two equations $B=12$

Determine the other constant: $A=-B-6=-12-6=-18$

Thus we then obtain:$G\left(x\right)=\frac{-18}{3x-1}+\frac{12}{2x-1}=\frac{18}{1-3x}-\frac{12}{1-2x}$

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

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

Therefore,$a_k=18·3^k-12·2^k$