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

Europe

Answers without the blur. Sign up and see all textbooks for free! Q4E

Expert-verified Found in: Page 549 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Find a closed form for the generating function for each of these sequences. (Assume a general form for the terms of the sequence, using the most obvious choice of such a sequence.)a) $$- 1, - 1, - 1, - 1, - 1, - 1, - 1,0,0,0,0,0,0, \ldots$$b) $$1,3,9,27,81,243,729, \ldots$$c) $$0,0,3, - 3,3, - 3,3, - 3, \ldots$$d) $$1,2,1,1,1,1,1,1,1, \ldots$$e) $$\left( {\begin{array}{*{20}{l}}7\\0\end{array}} \right),2\left( {\begin{array}{*{20}{l}}7\\1\end{array}} \right),{2^2}\left( {\begin{array}{*{20}{l}}7\\2\end{array}} \right), \ldots ,{2^7}\left( {\begin{array}{*{20}{l}}7\\7\end{array}} \right),0,0,0,0, \ldots$$f) $$- 3,3, - 3,3, - 3,3, \ldots$$g) $$0,1, - 2,4, - 8,16, - 32,64, \ldots$$h) $$1,0,1,0,1,0,1,0, \ldots$$

(a) The required result is$$- \frac{{1 - {x^7}}}{{1 - x}}$$.

(b) The required result is$$\frac{1}{{1 - 3x}}$$.

(c) The required result is$$\frac{{3{x^2}}}{{1 + x}}$$.

(d) The required result is$$x + \frac{1}{{1 - x}}$$.

(e) The required result is$${(1 + 2x)^7}$$.

(f) The required result is$$\frac{{ - 3}}{{1 + x}}$$.

(g) The required result is$$\frac{x}{{1 + 2x}}$$.

(h) The required result is$$\frac{1}{{1 - {x^2}}}$$.

See the step by step solution

## Step 1: Formula of generating function

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

## Step 2: Use the definition of a generating function and solve the sequence

For the sequence:

$$- 1, - 1, - 1, - 1, - 1, - 1, - 1,0,0,0,0,0,0, \ldots$$

Use the formula for generating function:

$\begin{array}{l}G(x) = - 1 - x - {x^2} - \ldots - {x^6} + 0{x^7} + 0{x^8} + \ldots \\G(x) = - 1 - x - {x^2} - \ldots - {x^6}\\G(x) = - \sum\limits_{k = 0}^6 {{x^k}} \\G(x) = - \frac{{1 - {x^7}}}{{1 - x}}\end{array}$

## Step 3: Use the definition of a generating function and solve the sequence

For the sequence:

$$1,3,9,27,81,243,729, \ldots$$

Use the formula for generating function:

$$\begin{array}{l}G(x) = 1 + 3x + 9{x^2} + 27{x^3} + 81{x^4} + 243{x^5} + 729{x^6} + ..\\G(x) = {3^0} + {3^1}x + {3^2}{x^2} + {3^3}{x^3} + {3^4}{x^4} + {3^5}{x^5} + {3^6}{x^6} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{{(3x)}^k}} \\G(x) = \frac{1}{{1 - 3x}}\end{array}$$

## Step 4: Use the definition of a generating function and solve the sequence

For the sequence:

$$0,0,3, - 3,3, - 3,3, - 3, \ldots$$

Use the formula for generating function:

$$\begin{array}{l}G(x) = 0 + 0x + 3{x^2} - 3{x^3} + 3{x^4} - 3{x^5} + 3{x^6} + \ldots \\G(x) = 3{( - 1)^2}{x^2} + 3{( - 1)^3}{x^3} + 3{( - 1)^4}{x^4} + 3{( - 1)^5}{x^5} + 3{( - 1)^6}{x^6} + \ldots \\G(x) = \sum\limits_{k = 2}^{ + \infty } 3 {( - 1)^k}{x^k}\end{array}$$

$$\begin{array}{l}G(x) = 3{x^2} \cdot \frac{1}{{1 - ( - x)}}\\G(x) = \frac{{3{x^2}}}{{1 + x}}\end{array}$$

## Step 5: Use the definition of a generating function and solve the sequence

For the sequence:

$$1,2,1,1,1,1,1,1,1, \ldots$$

Use the formula for generating function:

$$\begin{array}{l}G(x) = 1 + 2x + 1{x^2} + 1{x^3} + 1{x^4} + 1{x^5} + \ldots \\G(x) = 1 + 2x + {x^2} + {x^3} + {x^4} + {x^5} + \ldots \\G(x) = x + \left( {1 + x + {x^2} + {x^3} + {x^4} + {x^5} + \ldots } \right)\end{array}$$

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

## Step 6: Use the definition of a generating function and solve the sequence

For the sequence:

$$\left( {\begin{array}{*{20}{l}}7\\0\end{array}} \right),2\left( {\begin{array}{*{20}{l}}7\\1\end{array}} \right),{2^2}\left( {\begin{array}{*{20}{l}}7\\2\end{array}} \right), \ldots ,{2^7}\left( {\begin{array}{*{20}{l}}7\\7\end{array}} \right),0,0,0,0, \ldots$$

Use the formula for generating function:

$$G(x) = \left( {\begin{array}{*{20}{l}}7\\0\end{array}} \right) + 2\left( {\begin{array}{*{20}{l}}7\\1\end{array}} \right)x + {2^2}\left( {\begin{array}{*{20}{l}}7\\2\end{array}} \right){x^2} + {2^3}\left( {\begin{array}{*{20}{l}}7\\3\end{array}} \right){x^3} + {2^4}\left( {\begin{array}{*{20}{l}}7\\4\end{array}} \right){x^4} + {2^5}\left( {\begin{array}{*{20}{l}}7\\5\end{array}} \right){x^5} + {2^6}\left( {\begin{array}{*{20}{l}}7\\6\end{array}} \right){x^6} + {2^7}\left( {\begin{array}{*{20}{l}}7\\7\end{array}} \right){x^7} + 0{x^8} + 0{x^9} + \ldots .$$

$$G(x) = \left( {\begin{array}{*{20}{l}}7\\0\end{array}} \right) + \left( {\begin{array}{*{20}{l}}7\\1\end{array}} \right)2x + \left( {\begin{array}{*{20}{l}}7\\2\end{array}} \right){(2x)^2} + \left( {\begin{array}{*{20}{l}}7\\3\end{array}} \right){(2x)^3} + \left( {\begin{array}{*{20}{l}}7\\4\end{array}} \right){(2x)^4} + \left( {\begin{array}{*{20}{l}}7\\5\end{array}} \right){(2x)^5} + \left( {\begin{array}{*{20}{l}}7\\6\end{array}} \right){(2x)^6} + \left( {\begin{array}{*{20}{l}}7\\7\end{array}} \right){(2x)^7}$$

$$G(x) = \sum\limits_{k = 0}^7 {\left( {\begin{array}{*{20}{l}}7\\k\end{array}} \right)} {(2x)^k}$$

$$G(x) = {(1 + 2x)^7}$$

## Step 7: Use the definition of a generating function and solve the sequence

For the sequence:

$$- 3,3, - 3,3, - 3,3, \ldots$$

Use the formula for generating function:

$$\begin{array}{l}G(x) = - 3 + 3x - 3{x^2} + 3{x^3} - 3{x^4} + 3{x^5} + \ldots \\G(x) = 3{( - 1)^1} + 3{( - 1)^2}x + 3{( - 1)^3}{x^2} + 3{( - 1)^4}{x^3} + 3{( - 1)^5}{x^4} + 3{( - 1)^6}{x^5} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } 3 \cdot {( - 1)^{k + 1}}{x^k}\\G(x) = - 3\sum\limits_{k = 0}^{ + \infty } {{{( - x)}^k}} \end{array}$$

$$\begin{array}{l}G(x) = - 3 \cdot \frac{1}{{1 - ( - x)}}\\G(x) = \frac{{ - 3}}{{1 + x}}\end{array}$$

## Step 8: Use the definition of a generating function and solve the sequence

For the sequence:

$$0,1, - 2,4, - 8,16, - 32,64, \ldots$$

Use the formula for generating function:

$$\begin{array}{l}G(x) = 0 + 1x - 2{x^2} + 4{x^3} - 8{x^4} + 16{x^5} + \ldots \\G(x) = {( - 2)^0}x + {( - 2)^1}{x^2} + {( - 2)^2}{x^3} + {( - 2)^3}{x^4} + {( - 2)^4}{x^5} + \ldots \\G(x) = \sum\limits_{k = 1}^{ + \infty } {{{( - 2)}^{k - 1}}} {x^k}\end{array}$$

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

## Step 9: Use the definition of a generating function and solve the sequence

For the sequence:

$$1,0,1,0,1,0,1,0, \ldots$$

Use the formula for generating function:

$$\begin{array}{l}G(x) = 1 + 0x + 1{x^2} + 0{x^3} + 1{x^4} + 0{x^5} + \ldots \\G(x) = 1 + {x^2} + {x^4} + {x^6} + \ldots \\G(x) = \sum\limits_{k = 0}^{ + \infty } {{x^{2k}}} \end{array}$$

$$\begin{array}{l}G(x) = \sum\limits_{k = 0}^{ + \infty } {{{\left( {{x^2}} \right)}^k}} \\G(x) = \frac{1}{{1 - {x^2}}}\end{array}$$ ### Want to see more solutions like these? 