• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q7E

Expert-verified
Found in: Page 549

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

For each of these generating functions, provide a closed formula for the sequence it determines.a) $${(3x - 4)^3}$$b) $${\left( {{x^3} + 1} \right)^3}$$c) $$1/(1 - 5x)$$d) $${x^3}/(1 + 3x)$$e) $${x^2} + 3x + 7 + \left( {1/\left( {1 - {x^2}} \right)} \right)$$f) $$\left( {{x^4}/\left( {1 - {x^4}} \right)} \right) - {x^3} - {x^2} - x - 1$$g) $${x^2}/{(1 - x)^2}$$h) $$2{e^{2x}}$$

(a) The required result is$${a_0} = - 64,{a_1} = 144,{a_2} = - 108,{a_3} = 27,{a_n} = 0$$ when$$n \ge 4$$.

(b) The required result is$${a_0} = 1,{a_3} = 3,{a_6} = 3,{a_9} = 1,{a_n} = 0$$ when $$n = 1,2,4,5,7,8$$ and$$n \ge 10$$.

(c) The required result is$${a_n} = {5^n},n = 0,1,2, \ldots$$

(d) The required result is$${a_0} = 0,{a_1} = 0,{a_2} = 0,{a_n} = {( - 3)^{n - 3}},n = 3,4,5, \ldots$$

(e) The required result is$${a_0} = 8,{a_1} = 3,{a_2} = 2,{a_n} = 1$$ when $$n$$ even and $$n > 2,{a_n} = 0$$ otherwise.

(f) The required result is$${a_0} = - 1,{a_1} = - 1,{a_2} = - 1,{a_3} = - 1,{a_n} = 1$$ when $$n$$ is a multiple of 4 and $$n \ge 4,{a_n} = 0$$ otherwise.

(g) The required result is$${a_0} = {a_1} = 0,{a_n} = n - 1$$ when$$n \ge 2$$.

(h) The required result is$${a_n} = \frac{{{2^{n + 1}}}}{{n!}},n = 0,1,2, \ldots$$

See the step by step solution

Step 1: Formula of generating function and binomial theorem

Generating function for the sequence $${a_0},{a_1}, \ldots ,{a_k}$$of real numbers is the infinite series

$$G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}$$

Binomial theorem:

$${(x + y)^n} = \sum\limits_{j = 0}^n {\left( {\begin{array}{*{20}{l}}n\\j\end{array}} \right)} {x^{n - j}}{y^j}$$

Step 2: Use the definition of a generating function and binomial theorem to solve the sequence

For the sequence:

$${(3x - 4)^3}$$

Use binomial theorem:

$$\begin{array}{l}{(3x - 4)^3} = {(3x + ( - 4))^3}\\{(3x - 4)^3} = \left( {\begin{array}{*{20}{l}}3\\0\end{array}} \right){(3x)^{3 - 0}}{( - 4)^0} + \left( {\begin{array}{*{20}{l}}3\\1\end{array}} \right){(3x)^{3 - 1}}{( - 4)^1} + \left( {\begin{array}{*{20}{l}}3\\2\end{array}} \right){(3x)^{3 - 2}}{( - 4)^2} + \left( {\begin{array}{*{20}{l}}3\\3\end{array}} \right){(3x)^{3 - 3}}{( - 4)^3}\\{(3x - 4)^3} = 27{x^3} - 108{x^2} + 144x - 64\end{array}$$

The generating function is of the form:

$$\begin{array}{l}G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\end{array}$$

$$\begin{array}{l}{a_0} = - 64\\{a_1} = 144\\{a_2} = - 108\end{array}$$

$$\begin{array}{l}{a_3} = 27\\{a_n} = 0{\rm{ when }}n \ge 4\end{array}$$

Step 3: Use the definition of a generating function and binomial theorem to solve the sequence

For the sequence:

$${\left( {{x^3} + 1} \right)^3}$$

Use the binomial theorem:

$$\begin{array}{l}{\left( {{x^3} + 1} \right)^3} = \left( {\begin{array}{*{20}{l}}3\\0\end{array}} \right){\left( {{x^3}} \right)^{3 - 0}}{(1)^0} + \left( {\begin{array}{*{20}{l}}3\\1\end{array}} \right){\left( {{x^3}} \right)^{3 - 1}}{(1)^1} + \left( {\begin{array}{*{20}{l}}3\\2\end{array}} \right){\left( {{x^3}} \right)^{3 - 2}}{(1)^2} + \left( {\begin{array}{*{20}{l}}3\\3\end{array}} \right){\left( {{x^3}} \right)^{3 - 3}}{(1)^3}\\{\left( {{x^3} + 1} \right)^3} = {x^9} + 3{x^6} + 3{x^3} + 1\end{array}$$

The generating function is of the form:

$$\begin{array}{l}G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\end{array}$$

$${a_0} = 1$$

$${a_3} = 3$$

$${a_6} = 3$$

$${a_9} = 1$$

$${a_n} = 0$$ when $$n = 1,2,4,5,7,8$$ and $$n \ge 10$$

Step 4: Use the definition of a generating function and binomial theorem to solve the sequence

For the sequence:

$$1/(1 - 5x)$$

Use the fact: $$\sum\limits_{k = 0}^{ + \infty } {{x^k}} = \frac{1}{{1 - x}}$$

$$\begin{array}{l}\frac{1}{{1 - 5x}} = \sum\limits_{k = 0}^{ + \infty } {{{(5x)}^k}} \\\frac{1}{{1 - 5x}} = \sum\limits_{k = 0}^{ + \infty } {{5^k}} {x^k}\end{array}$$

The generating function is of the form:

$$\begin{array}{l}G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\end{array}$$

$$\begin{array}{l}{a_n} = {5^n}\\n = 0,1,2, \ldots \end{array}$$

Step 5: Use the definition of a generating function and binomial theorem to solve the sequence

For the sequence:

$${x^3}/(1 + 3x)$$

Use the fact: $$\sum\limits_{k = 0}^{ + \infty } {{x^k}} = \frac{1}{{1 - x}}$$

$$\frac{{{x^3}}}{{1 + 3x}} = {x^3} \cdot \frac{1}{{1 - ( - 3x)}}$$

$$\frac{{{x^3}}}{{1 + 3x}} = \sum\limits_{m = 3}^{ + \infty } {{{( - 3)}^{m - 3}}{x^m}}$$

The generating function is of the form:

$$\begin{array}{l}G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\end{array}$$

$$\begin{array}{l}{a_0} = 0\\{a_1} = 0\\{a_2} = 0\end{array}$$

$$\begin{array}{l}{a_n} = {( - 3)^{n - 3}}\,\\n = 3,4,5, \ldots \end{array}$$

Step 6: Use the definition of a generating function and binomial theorem to solve the sequence

For the sequence:

$${x^2} + 3x + 7 + \left( {1/\left( {1 - {x^2}} \right)} \right)$$

Use the fact: $$\sum\limits_{k = 0}^{ + \infty } {{x^k}} = \frac{1}{{1 - x}}$$

$${x^2} + 3x + 7 + \frac{1}{{1 - {x^2}}} = {x^2} + 3x + 7 + \sum\limits_{k = 0}^{ + \infty } {{{\left( {{x^2}} \right)}^k}}$$

$${x^2} + 3x + 7 + \frac{1}{{1 - {x^2}}} = 8 + 3x + 2{x^2} + \sum\limits_{k = 2}^{ + \infty } {{x^{2k}}}$$

The generating function is of the form:

$$\begin{array}{l}G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\end{array}$$

$${a_0} = 8$$

$${a_1} = 3$$

$${a_2} = 2$$

$${a_n} = 1$$ when $$n$$ even and$$n > 2$$.

$${a_n} = 0$$ otherwise.

Step 7: Use the definition of a generating function and binomial theorem to solve the sequence

For the sequence:

$$\left( {{x^4}/\left( {1 - {x^4}} \right)} \right) - {x^3} - {x^2} - x - 1$$

Use the fact: $$\sum\limits_{k = 0}^{ + \infty } {{x^k}} = \frac{1}{{1 - x}}$$

$$\frac{{{x^4}}}{{1 - {x^4}}} - {x^3} - {x^2} - x - 1 = {x^4} \cdot \frac{1}{{1 - {x^4}}} - {x^3} - {x^2} - x - 1$$

$$\frac{{{x^4}}}{{1 - {x^4}}} - {x^3} - {x^2} - x - 1 = - 1 - x - {x^2} - {x^3} + \sum\limits_{m = 1}^{ + \infty } {{x^{4m}}}$$

The generating function is of the form:

$$\begin{array}{l}G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\end{array}$$

$${a_0} = - 1$$

$${a_1} = - 1$$

$${a_2} = - 1$$

$${a_3} = - 1$$

$${a_n} = 1$$ when $$n$$ is a multiple of 4 and$$n \ge 4$$.

$${a_n} = 0$$ otherwise.

Step 8: Use the definition of a generating function and binomial theorem to solve the sequence

For the sequence:

$${x^2}/{(1 - x)^2}$$

Use the fact: $$\sum\limits_{k = 0}^{ + \infty } {{x^k}} = \frac{1}{{1 - x}}$$

$$\frac{{{x^2}}}{{{{(1 - x)}^2}}} = {x^2} \cdot \frac{1}{{{{(1 - x)}^2}}}$$

$$\frac{{{x^2}}}{{{{(1 - x)}^2}}} = \sum\limits_{m = 2}^{ + \infty } {(m - 1)} {x^m}$$

The generating function is of the form:

$$\begin{array}{l}G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\end{array}$$

$${a_0} = {a_1} = 0$$

$${a_n} = n - 1$$ when$$n \ge 2$$.

Step 9: Use the definition of a generating function and binomial theorem to solve the sequence

For the sequence:

$$2{e^{2x}}$$

Use the fact: $$\sum\limits_{k = 0}^{ + \infty } {{x^k}} = \frac{1}{{1 - x}}$$

$$\begin{array}{l}2{e^{2x}} = 2\sum\limits_{k = 0}^{ + \infty } {\frac{{{{(2x)}^k}}}{{k!}}} \\2{e^{2x}} = 2\sum\limits_{k = 0}^{ + \infty } {\frac{{{2^k}}}{{k!}}} \cdot {x^k}\\2{e^{2x}} = \sum\limits_{k = 0}^{ + \infty } {\frac{{{2^{k + 1}}}}{{k!}}} \cdot {x^k}\end{array}$$

The generating function is of the form:

$$\begin{array}{l}G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\end{array}$$

$$\begin{array}{l}{a_n} = \frac{{{2^{n + 1}}}}{{n!}}\\n = 0,1,2, \ldots \end{array}$$