Chapter 8: Q35E (page 536)
Give a big- estimate for the function in Exerciseifis an increasing function.
The required result is
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Find the coefficient of \({x^{12}}\) in the power series of each of these functions.
a) \(1/(1 + 3x)\)
b) \(1/(1 + 3x)\)
c) \(1/{(1 + x)^8}\)
d) \(1/{(1 - 4x)^3}\)
e) \({x^3}/{(1 + 4x)^2}\)
Find the sequence with each of these functions as its exponential generating function
Find a closed form for the generating function for each of these sequences. (For each sequence, use the most obvious choice of a sequence that follows the pattern of the initial terms listed.)
a) \(0,2,2,2,2,2,2,0,0,0,0,0, \ldots \)
b) \(0,0,0,1,1,1,1,1,1, \ldots \)
c) \(0,1,0,0,1,0,0,1,0,0,1, \ldots \)
d) \(2,4,8,16,32,64,128,256, \ldots \)
e) \(\left( {\begin{array}{*{20}{l}}7\\0\end{array}} \right),\left( {\begin{array}{*{20}{l}}7\\1\end{array}} \right),\left( {\begin{array}{*{20}{l}}7\\2\end{array}} \right), \ldots ,\left( {\begin{array}{*{20}{l}}7\\7\end{array}} \right),0,0,0,0,0, \ldots \)
f) \(2, - 2,2, - 2,2, - 2,2, - 2, \ldots \)
g) \(1,1,0,1,1,1,1,1,1,1, \ldots \)
h) \(0,0,0,1,2,3,4, \ldots \)
For each of these generating functions, provide a closed formula for the sequence it determines.
a) \({\left( {{x^2} + 1} \right)^3}\)
b) \({(3x - 1)^3}\)
c) \(1/\left( {1 - 2{x^2}} \right)\)
d) \({x^2}/{(1 - x)^3}\)
e) \(x - 1 + (1/(1 - 3x))\)
f) \(\left( {1 + {x^3}} \right)/{(1 + x)^3}\)
g) \(x/\left( {1 + x + {x^2}} \right)\)
h) \({e^{3{x^2}}} - 1\)
Set up a divide-and-conquer recurrence relation for the number of modular multiplications required to compute \({a^n}\,\bmod \,\;m,\) where\(a,\;n\), and \(n\) are positive integers, using the recursive algorithms from Example 4 in Section 5.4.
b) Use the recurrence relation you found in part (a) to construct a big-\(O\)estimate for the number of modular multiplications used to compute\({a^n}\,\bmod \,\;m\)using the recursive algorithm.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
