• :00Days
  • :00Hours
  • :00Mins
  • 00Seconds
A new era for learning is coming soonSign up for free
Log In Start studying!

Select your language

Suggested languages for you:
Deutsch (DE)
Deutsch (UK)
Deutsch (US)

Americas

Europe

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

Q4E

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

Discrete Mathematics and its Applications

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

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later
Illustration

Short Answer

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 by Step Solution

TABLE OF CONTENTS :
TABLE OF CONTENTS

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

Most popular questions for Math Textbooks

Find\(f(n)\) when \(n = {2^k}\), where\(f\)satisfies the recurrence relation \(f(n) = 8f(n/2) + {n^2}\) with\(f(1) = 1\).

Explain how generating functions can be used to find the number of ways in which postage of r cents can be pasted on an envelope using 3-cent, 4-cent, and 20-cent stamps.

a) Assume that the order the stamps are pasted on does not matter.

b) Assume that the stamps are pasted in a row and the order in which they are pasted on matters.

c) Use your answer to part (a) to determine the number of ways 46 cents of postage can be pasted on an envelope using 3 -cent, 4-cent, and 20-cent stamps when the order the stamps are pasted on does not matter. (Use of a computer algebra program is advised.)

d) Use your answer to part (b) to determine the number of ways 46 cents of postage can be pasted in a row on an envelope using 3-cent, 4 -cent, and 20 -cent stamps when the order in which the stamps are pasted on matters.

Multiply (1110)2and (1010)2 using the fast multiplication algorithm.

A sequence \({a_1},{a_2},.....,{a_n}\) is unimodal if and only if there is an index \(m,1 \le m \le n,\) such that \({a_i} < {a_i} + 1\) when \(1{1 < i < m}\) and \({a_i} > {a_{i + 1}}\) when \(m \le i < n\). That is, the terms of the sequence strictly increase until the \(m\)th term and they strictly decrease after it, which implies that \({a_m}\) is the largest term. In this exercise, \({a_m}\) will always denote the largest term of the unimodal sequence \({a_1},{a_2},.....,{a_n}\).

a) Show that \({a_m}\) is the unique term of the sequence that is greater than both the term immediately preceding it and the term immediately following it.

b) Show that if \({a_i} < {a_i} + 1\) where \(1 \le i < n\), then \(i + 1 \le m \le n\).

c) Show that if \({a_i} > {a_{i + 1}}\) where \(1 \le i < n\), then \(1 \le m \le i\).

d) Develop a divide-and-conquer algorithm for locating the index \(m\). (Hint: Suppose that \(i < m < j\). Use parts (a), (b), and (c) to determine whether \(((i + j)/2) + 1 \le m \le n,\) \(1 \le m \le ((i + j)/2) - 1,\) or \(m = ((i + j)/2)\)

Use generating functions to solve the recurrence relation ak=ak-1+2ak-2+2k with initial conditions a0=4 anda1=12.
Icon

Want to see more solutions like these?

Sign up for free to discover our expert answers
Get Started - It’s free

Recommended explanations on Math Textbooks

Decision Maths

Read explanation

Calculus

Read explanation

Probability and Statistics

Read explanation

Statistics

Read explanation

Mechanics Maths

Read explanation

Geometry

Read explanation

Pure Maths

Read explanation

94% of StudySmarter users get better grades.

Sign up for free
94% of StudySmarter users get better grades.