Question

Find a closed form for the generating function for the sequence\(\left\{ {{a_n}} \right\}\), where

a) \({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 \)

Short answer

(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)\).

Step-by-step solution

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

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

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

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

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

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

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