Question

If G(x) is the generating function for the sequence$\left\{a_k\right\}$, what is the generating function for each of these sequences?

a) $\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}{\mathit{a}}_{\mathbf{3}}\mathbf{,}{\mathit{a}}_{\mathbf{4}}\mathbf{,}{\mathit{a}}_{\mathbf{5}}\mathbf{,}\mathbf{\dots }$(Assuming that terms follow the pattern of all but the first three terms)

b)${\mathit{a}}_{\mathbf{0}}\mathbf{,}\mathbf{0}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{,}\mathbf{0}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{\dots }$

c) $\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}{\mathit{a}}_{\mathbf{0}}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }$(Assuming that terms follow the pattern of all but the first four terms)

d)${\mathit{a}}_{\mathbf{0}}\mathbf{,}\mathbf{2}{\mathit{a}}_{\mathbf{1}}\mathbf{,}\mathbf{4}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{8}{\mathit{a}}_{\mathbf{3}}\mathbf{,}\mathbf{16}{\mathit{a}}_{\mathbf{4}}\mathbf{,}\mathbf{\dots }$

e) $\mathbf{0}\mathbf{,}{\mathit{a}}_{\mathbf{0}}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{/}\mathbf{2}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{/}\mathbf{3}\mathbf{,}{\mathit{a}}_{\mathbf{3}}\mathbf{/}\mathbf{4}\mathbf{,}\mathbf{\dots }$ [Hint: Calculus required here.]

f) ${\mathit{a}}_{\mathbf{0}}\mathbf{,}{\mathit{a}}_{\mathbf{0}}\mathbf{+}{\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{0}}\mathbf{+}{\mathit{a}}_{\mathbf{1}}\mathbf{+}{\mathit{a}}_{\mathbf{2}}\mathbf{,}{\mathit{a}}_{\mathbf{0}}\mathbf{+}{\mathit{a}}_{\mathbf{1}}\mathbf{+}{\mathit{a}}_{\mathbf{2}}\mathbf{+}{\mathit{a}}_{\mathbf{3}}\mathbf{,}\mathbf{\dots }$

Short answer

The generating function for each of the given sequences is:

(a)$G\left(x\right)-a_0-a_{1}x-a_2{x}^2$

(b)$G\left(x^2\right)$

(c)$x^{4}G\left(x\right)$

(d)$G\left(2x\right)$

(e)$\int G\left(x\right)dx$

(f)$\frac{G\left(x\right)}{1-x}$

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

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

The given sequence is:

$0,0,0,a_3,a_4,a_5,\dots$

By generating function:

$$\begin{gathered} G_a\left(x\right)=0+0x+0x^2+a_3{x}^3+a_4{x}^4+a_5{x}^5+\dots \\ =a_3{x}^3+a_4{x}^4+a_5{x}^5+\dots \\ =-a_0-a_{1}x-a_2{x}^2+a_0+a_{1}x+a_2{x}^2+a_3{x}^3+a_4{x}^4+a_5{x}^5+\dots \\ =-a_0-a_{1}x-a_2{x}^2+\sum _{k=0}^{+\infty }{a}_k{x}^k \\ =-a_0-a_{1}x-a_2{x}^2+G\left(x\right) \\ =G\left(x\right)-a_0-a_{1}x-a_2{x}^2 \end{gathered}$$

Use Generating Function:

G(x) is the generating function for the sequence $\left\{a_k\right\}$$G\left(x\right)=a_0+a_{1}x+a_2{x}^2+\dots +a_k{x}^k+\dots =\sum _{k=0}^{+\infty }{a}_k{x}^k$

The given sequence is:

$a_0,0,a_1,0,a_2,0,\dots$

By generating function:

$$\begin{gathered} G_a\left(x\right)=a_0+0x+a_1{x}^2+0x^3+a_2{x}^4+0x^5+\dots \\ =a_0+a_1{x}^2+a_2{x}^4+\dots . \\ =a_0+a_{1}y+a_2{y}^2+\dots . \\ =\sum _{k=0}^{+\infty }{a}_k{y}^k \\ =G\left(y\right)(Lety=x^2) \\ =G\left(x^2\right) \end{gathered}$$

Use Generating Function:

G(x) is the generating function for the sequence $\left\{a_k\right\}$$G\left(x\right)=a_0+a_{1}x+a_2{x}^2+\dots +a_k{x}^k+\dots =\sum _{k=0}^{+\infty }{a}_k{x}^k$

The given sequence is:

$0,0,0,0,a_0,a_1,a_2,\dots$

By generating function:

$$\begin{gathered} G_a\left(x\right)=0+0x+0x^2+0x^3+a_0{x}^4+a_1{x}^5+a_2{x}^6+\dots \\ =a_0{x}^4+a_1{x}^5+a_2{x}^6+\dots \\ =x^4\left(a_0+a_{1}x+a_2{x}^2+\dots .\right) \\ =x^4\sum _{k=0}^{+\infty }{a}_k{x}^k \\ =x^{4}G\left(x\right) \end{gathered}$$

Use Generating Function:

G(x) is the generating function for the sequence $\left\{a_k\right\}$$G\left(x\right)=a_0+a_{1}x+a_2{x}^2+\dots +a_k{x}^k+\dots =\sum _{k=0}^{+\infty }{a}_k{x}^k$

$a_0,2a_1,4a_2,8a_3,16a_4,\dots$

By generating function:

$$\begin{gathered} G_a\left(x\right)=a_0+2a_{1}x+4a_2{x}^2+8a_3{x}^3+\dots \\ =a_0+a_1\left(2x\right)+a_2{\left(2x\right)}^2+a_3{\left(2x\right)}^3+\dots Lety=2x \\ =a_0+a_{1}y+a_2{y}^2+\dots \\ =\sum _{k=0}^{+\infty }{a}_k{y}^k \\ =G\left(y\right) \\ =G\left(2x\right) \end{gathered}$$

Use Generating Function:

G(x) is the generating function for the sequence $\left\{a_k\right\}$$G\left(x\right)=a_0+a_{1}x+a_2{x}^2+\dots +a_k{x}^k+\dots =\sum _{k=0}^{+\infty }{a}_k{x}^k$

The given sequence is:

$0,a_0,a_1/2,a_2/3,a_3/4,\dots$

Take the integral with respect to x :

$$\begin{gathered} \int G\left(x\right)dx=a_{0}x+\frac{a_1}{2}x+\frac{a_2}{3}{x}^2+\frac{a_3}{4}{x}^3+\dots \\ =0+a_{0}x+\frac{a_1}{2}x+\frac{a_2}{3}{x}^2+\frac{a_3}{4}{x}^3+ \end{gathered}$$

Therefore$\int G\left(x\right)dx$ is the generating function of the given sequence.

Use the Theorem of addition and multiplication of generating functions.

If $f\left(x\right)=\sum _{k=0}^{+\infty }{a}_k{x}^k$and $g\left(x\right)=\sum _{k=0}^{+\infty }{b}_k{x}^k$, then $f\left(x\right)·g\left(x\right)=\sum _{k=0}^{+\infty }\left(\sum _{j=0}^k{a}_j{b}_{k-j}\right)x^k$

The given sequence is:

$a_0,a_0+a_1,a_0+a_1+a_2,a_0+a_1+a_2+a_3,\dots$

The given sequence is of the form $\sum _{k=0}^{+\infty }\left(\sum _{j=0}^k{a}_j\right)x^k$and thus $b_{k-j}=1$for all values of $k$&$j$.

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

$$\begin{gathered} \sum _{k=0}^{+\infty }\left(\sum _{j=0}^k{a}_j\right)x^k=G\left(x\right)·h\left(x\right) \\ =G\left(x\right)·\sum _{k=0}^{+\infty }{x}^k \\ =G\left(x\right)·\frac{1}{1-x}\sum _{k=0}^{+\infty }{x}^k \\ =\frac{1}{1-x} \\ =\frac{G\left(x\right)}{1-x} \end{gathered}$$

Thus,$G^2\left(x\right)=G\left(x\right)·G\left(x\right)$ has the required sequence of coefficients.