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

Suggested languages for you:

Americas

Europe

Q6E

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 the sequence$$\left\{ {{a_n}} \right\}$$, wherea) $${a_n} = - 1$$ for all$$n = 0,1,2, \ldots$$.b) $${a_n} = {2^n}$$for$$n = 1,2,3,4, \ldots$$and$${a_0} = 0$$.c) $${a_n} = n - 1$$for$$n = 0,1,2, \ldots$$.d) $${a_n} = 1/(n + 1)!$$for$$n = 0,1,2, \ldots$$e) $${a_n} = \left( {\begin{array}{*{20}{l}}n\\2\end{array}} \right)$$for$$n = 0,1,2, \ldots$$f) $${a_n} = \left( {\begin{array}{*{20}{c}}{10}\\{n + 1}\end{array}} \right)$$for$$n = 0,1,2, \ldots$$

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

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

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

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

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

(f) The required result is$$\frac{1}{x}\left( {{{(1 + x)}^{10}} - 1} \right)$$.

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:

$${a_n} = - 1$$ for all$$n = 0,1,2, \ldots$$.

Use the formula for generating function:

$$\begin{array}{c}G(x) = - 1 - x - {x^2} - \ldots \\G(x) = - \left( {1 + x + {x^2} + \ldots } \right)\\G(x) = - \sum\limits_{k = 0}^{ + \infty } {{x^k}} \\G(x) = - \frac{1}{{1 - x}}\\G(x) = \frac{1}{{x - 1}}\end{array}$$

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

For the sequence:

$${a_n} = {2^n}$$ for $$n = 1,2,3,4, \ldots$$ and$${a_0} = 0$$.

Use the formula for generating function:

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

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

For the sequence:

$${a_n} = n - 1$$ for$$n = 0,1,2, \ldots$$.

Use the formula for generating function:

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

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

For the sequence:

$${a_n} = 1/(n + 1)!$$ for $$n = 0,1,2, \ldots$$

Use the formula for generating function:

$$\begin{array}{c}G(x) = \sum\limits_{k = 0}^{ + \infty } {\frac{1}{{(k + 1)!}}} {x^k}\\G(x) = \frac{1}{x}\sum\limits_{k = 0}^{ + \infty } {\frac{{{x^{k + 1}}}}{{(k + 1)!}}} \\G(x) = \frac{1}{x}\sum\limits_{m = 1}^{ + \infty } {\frac{{{x^m}}}{{m!}}} \\G(x) = \frac{1}{x}\left( {\sum\limits_{m = 0}^{ + \infty } {\frac{{{x^m}}}{{m!}}} - 1} \right)\\G(x) = \frac{1}{x}\left( {{e^x} - 1} \right)\\G(x) = \frac{{{e^x} - 1}}{x}\end{array}$$

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

For the sequence:

$${a_n} = \left( {\begin{array}{*{20}{l}}n\\2\end{array}} \right)$$ for $$n = 0,1,2, \ldots$$

Use the formula for generating function:

$$\begin{array}{l}G(x) = \left( {\begin{array}{*{20}{l}}0\\2\end{array}} \right) + \left( {\begin{array}{*{20}{l}}1\\2\end{array}} \right)x + \left( {\begin{array}{*{20}{l}}2\\2\end{array}} \right){x^2} + \ldots + \left( {\begin{array}{*{20}{l}}n\\2\end{array}} \right){x^n} + \ldots \\G(x) = \left( {\begin{array}{*{20}{l}}2\\2\end{array}} \right){x^2} + \ldots + \left( {\begin{array}{*{20}{l}}n\\2\end{array}} \right){x^n} + \ldots \end{array}$$

$$G(x) = {x^2}\sum\limits_{m = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{m + 2}\\2\end{array}} \right)} {x^m}$$

$$G(x) = {x^2}\sum\limits_{m = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{3 + m - 1}\\{3 - 1}\end{array}} \right)} {x^m}$$

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

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

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

For the sequence:

$${a_n} = \left( {\begin{array}{*{20}{c}}{10}\\{n + 1}\end{array}} \right)$$ for $$n = 0,1,2, \ldots$$

Use the formula for generating function:

$$\begin{array}{l}G(x) = \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{10}\\{k + 1}\end{array}} \right)} {x^k}\\G(x) = \sum\limits_{k = 0}^9 {\left( {\begin{array}{*{20}{c}}{10}\\{k + 1}\end{array}} \right)} {x^k}\\G(x) = \frac{1}{x}\sum\limits_{k = 0}^9 {\left( {\begin{array}{*{20}{c}}{10}\\{k + 1}\end{array}} \right)} {x^{k + 1}}\end{array}$$

$$\begin{array}{l}G(x) = \frac{1}{x}\sum\limits_{m = 1}^{10} {\left( {\begin{array}{*{20}{c}}{10}\\m\end{array}} \right)} {x^m}\\G(x) = \frac{1}{x}\left( {\sum\limits_{m = 0}^{10} {\left( {\begin{array}{*{20}{l}}{10}\\m\end{array}} \right)} {x^m} - 1} \right)\\G(x) = \frac{1}{x}\left( {{{(1 + x)}^{10}} - 1} \right)\end{array}$$