Let n be a variable that takes positive integer values. a. Show that n! is O(nn )

Graph each function defined in 1-8. \(f(x)=3^{x}\) for all real numbers x Text Transcription: f(x)=3^x

Graph each function defined in 1-8. \(g(x)=\left(\frac{1}{3}\right)^{x}\) for all real numbers x Text Transcription: g(x)=(frac 1 3)^x

Graph each function defined in 1-8. \(h(x)=\log _{10} x\) for all positive real numbers x Text Transcription: h(x)=log _10 x

Graph each function defined in 1-8. \(k(x)=\log _{2} x\) for all positive real numbers x Text Transcription: k(x)=log _2 x

Graph each function defined in 1-8. \(F(x)=\left\lfloor\log _{2} x\right\rfloor\) for all positive real numbers x Text Transcription: F(x) = lfloor log _2 x rfloor

Graph each function defined in 1-8. \(G(x)=\left\lceil\log _{2} x\right\rceil\) for all positive real numbers x Text Transcription: G(x)=lceil log _2 x rceil

Graph each function defined in 1-8. \(H(x)=x \log _{2} x\) for all positive real numbers x Text Transcription: H(x)=x log _2 x

Graph each function defined in 1-8. \(K(x)=x \log _{10} x\) for all positive real numbers x Text Transcription: K(x)=x log _10 x

The scale of the graph shown in Figure 11.4.1 is one-fourth inch to each unit. If the point \(\left(2,2^{64}\right)\) is plotted on the graph of \(y=2^{x}\), how many miles will it lie above the horizontal axis? What is the ratio of the height of the point to the distance of the earth from the sun? (There are 12 inches per foot and 5,280 feet per mile. The earth is approximately 93,000,000 miles from the sun on average.) \(\left(\frac{1}{4} \text { inch } \cong 0.635 \mathrm{~cm}, 1 \text { mile } \cong 0.62 \mathrm{~km}\right)\) Text Transcription: (2,2^64) y=2^x (frac 1 4 inch cong 0.635 cm, 1 mile cong 0.62 ~km)

a. Use the definition of logarithm to show that \(\log _{b} b^{x}=x\) for all real numbers x. b. Use the definition of logarithm to show that \(b^{\log _{b} x}=x\) for all positive real numbers x. c. By the result of exercise 25 in Section 7.3, if \(f: X \rightarrow Y\) and \(g: Y \rightarrow X\) are functions and \(g \circ f=I_{X}\) and \(f \circ g=\) \(I_{Y}\), then f and g are inverse functions. Use this result to show that \(\log _{b}\) and \(\exp _{b}\) (the exponential function with base b ) are inverse functions. Text Transcription: log _b b^x=x b^log _b x=x f: X \rightarrow Y g: Y \rightarrow X g \circ f=I_X f \circ g= I_Y log _b exp _b

Let b > 1. a. Use the fact that \(u=\log _{b} v \Leftrightarrow v=b^{u}\) to show that a point (u, v) lies on the graph of the logarithmic function with base b if, and only if, (v, u) lies on the graph of the exponential function with base b. b. Plot several pairs of points of the form (u, v) and (v, u) on a coordinate system. Describe the geometric relationship between the locations of the points in each pair. c. Draw the graphs of \(y=\log _{2} x\) and \(y=2^{x}\). Describe the geometric relationship between these graphs. Text Transcription: u=log _b v Leftrightarrow v=b^u y=log _2 x y=2^x

Give a graphical interpretation for property (11.4.2) in Example 11.4.1(a) for 0 < x < 1.

Suppose a positive real number x satisfies the inequality \(10^{m} \leq x<10^{m+1}\) where m is an integer. What can be inferred about \(\left\lfloor\log _{10} x\right\rfloor\)? Justify your answer. Text Transcription: 10^m leq x<10^m+1 lfloor log _10 x rfloor

a. Prove that if x is a positive real number and k is a nonnegative integer such that \(2^{k-1}<x \leq 2^{k}\), then \(\left\lceil\log _{2} x\right\rceil=k\). b. Describe in words the statement proved in part (a). Text Transcription: 2^k-1<x leq 2^k lceil log _2 x rceil=k

If n is an odd integer and n > 1, is \(\left\lceil\log _{2}(n-1)\right\rceil=\) \(\left\lceil\log _{2}(n)\right\rceil\) ? Justify your answer. Text Transcription: lceil log _2(n-1) rceil= lceil log _2(n) rceil

If n is an odd integeer and n > 1, is \(\left\lceil\log _{2}(n+1)\right\rceil=\) \(\left|\log _{2}(n)\right|\) ? Justify your answer. Text Transcription: lceil log _2(n+1) rceil= |log _2(n)|

If n is an odd integer and n > 1, is \(\left\lfloor\log _{2}(n+1)\right\rfloor=\) \(\left\lfloor\log _{2}(n)\right\rfloor\) ? Justify your answer. Text Transcription: lfloor log _2(n+1)rfloor=

In 18 and 19 , indicate how many binary digits are needed to represent the numbers in binary notation. Use the method shown in Example 11.4.3. 148,206

In 18 and 19 , indicate how many binary digits are needed to represent the numbers in binary notation. Use the method shown in Example 11.4.3. 5,067,329

It was shown in the text that the number of binary digits needed to represent a positive integer n is \(\left\lfloor\log _{2} n\right\rfloor+1\). Can this also be given as \(\left\lceil\log _{2} n\right\rceil\) ? Why or why not? Text Transcription: lfloor log _2 n rfloor+1 lceil log _2 n rceil

In each of 21 and 22 , a sequence is specified by a recurrence relation and initial conditions. In each case, (a) use iteration to guess an explicit formula for the sequence; (b) use strong mathematical induction to confirm the correctness of the formula you obtained in part (a). \(a_{k}=a_{\lfloor k / 2\rfloor}+2\), for all integers \(k \geq 2\) \(a_{1}=1\) Text Transcription: a_k=a_lfloor k / 2 rfloor+2 k geq 2 a_1=1

In each of 21 and 22 , a sequence is specified by a recurrence relation and initial conditions. In each case, (a) use iteration to guess an explicit formula for the sequence; (b) use strong mathematical induction to confirm the correctness of the formula you obtained in part (a). \(b_{k}=b_{[k / 2]}+1\), for all integers \(k \geq 2\) \(b_{1}=1\). Text Transcription: b_k=b_[k / 2]+1 k geq 2 b_1=1

Define a sequence \(c_{1}, c_{2}, c_{3}, \ldots\), recursively as follows: \(c_{1}=0\), \(c_{k}=2 c_{\lfloor k / 2\rfloor}+k, \quad \text { for all integers } k \geq 2\) . Use strong mathematical induction to show that \(c_{n} \leq n^{2}\) for all integers \(n \geq 1\). Text Transcription: c_1, c_2, c_3, ldots c_1=0 c_k=2 c_lfloor k / 2 rfloor+k, for all integers k geq 2 c_n leq n^2 n geq 1

Use strong mathematical induction to show that for the sequence of exercise 23, \(c_{n} \leq n \log _{2} n\), for all integers \(n \geq 4\). Text Transcription: c_n leq n log _2 n n geq 4

Exercises 25-28 refer to properties 11.4.9 and 11.4.10. To solve them, think big! Find a real number x > 3 such that \(\log _{2} x<x^{1 / 10}\). Text Transcription: log _2 x<x^1 / 10

Exercises 25-28 refer to properties 11.4.9 and 11.4.10. To solve them, think big! Find a real number x > 1 such that \(x^{50}<2^{x}\). Text Transcription: x^50<2^x

9780495391326_11.4_Exercise Set_28

Exercises 25-28 refer to properties 11.4.9 and 11.4.10. To solve them, think big! Use a graphing calculator or computer graphing program to find two distinct approximate values of x such that x = \(1.0001^{x}\). On what approximate intervals is \(x>1.0001^{x}\) ? On what approximate intervals is \(x<1.0001^{x}\) ? Text Transcription: 1.0001^x x>1.0001^x x<1.0001^x

Use \(\Theta\)-notation to express the following statement: \(\left|x^{2}\right| \leq\left|7 x^{2}+3 x \log _{2} x\right| \leq 10\left|x^{2}\right|\), for all real numbers x > 2. Text Transcription: Theta |x^2| leq|7 x^2+3 x log _2 x| leq 10|x^2|

Derive each statement in 30-33. \(2 x+\log _{2} x\) is \(\Theta(x)\). Text Transcription: 2x+log _2 x Theta(x)

Derive each statement in 30-33. \(x^{2}+5 x \log _{2} x\) is \(\Theta\left(x^{2}\right)\). Text Transcription: x^2+5 x log _2 x Theta(x^2)

Derive each statement in 30-33. \(n^{2}+2^{n}\) is \(\Theta\left(2^{n}\right)\). Text Transcription: n^2+2^n Theta(2^n)

Derive each statement in 30-33. \(2^{n+1}\) is \(\Theta\left(2^{n}\right)\). Text Transcription: 2^n+1 Theta(2^n)

Show that \(4^{n}\) is not \(O\left(2^{n}\right)\). Text Transcription: 4^n O(2^n)

Prove each of the statements in 35-40, assuming n is an integer variable that takes positive integer values. Use identities from Section 5.2 as needed. \(1+2+2^{2}+2^{3}+\cdots+2^{n}\) is \(\Theta\left(2^{n}\right)\). Text Transcription: 1+2+2^2+2^3+dots+2^n Theta(2^n)

Prove each of the statements in 35-40, assuming n is an integer variable that takes positive integer values. Use identities from Section 5.2 as needed. \(4+4^{2}+4^{3}+\cdots+4^{n}\) is \(\Theta\left(4^{n}\right)\). Text Transcription: 4+4^2+4^3+dots+4^n Theta(4^n)

Prove each of the statements in 35-40, assuming n is an integer variable that takes positive integer values. Use identities from Section 5.2 as needed. \(2+2 \cdot 3^{2}+2 \cdot 3^{4}+\cdots+2 \cdot 3^{2 n}\) is \(\Theta\left(3^{2 n}\right)\). Text Transcription: 2+2 dot 3^2+2 dot 3^4+dots+2 dot 3^2 n Theta(3^2 n)

Prove each of the statements in 35-40, assuming n is an integer variable that takes positive integer values. Use identities from Section 5.2 as needed. \(\frac{1}{5}+\frac{4}{5^{2}}+\frac{4^{2}}{5^{3}}+\cdots+\frac{4^{n}}{5^{n+1}}\) is \(\Theta(1)\). Text Transcription: frac 1 5+frac 4 5^2+frac 4^2 5^3+dots+frac 4^n 5^n+1 Theta(1)

Prove each of the statements in 35-40, assuming n is an integer variable that takes positive integer values. Use identities from Section 5.2 as needed. \(n+\frac{n}{2}+\frac{n}{4}+\cdots+\frac{n}{2^{n}}\) is \(\Theta(n)\). Text Transcription: n+frac n 2+frac n 4+dots+frac n 2^n Theta(n)

Prove each of the statements in 35-40, assuming n is an integer variable that takes positive integer values. Use identities from Section 5.2 as needed. \(\frac{2 n}{3}+\frac{2 n}{3^{2}}+\frac{2 n}{3^{3}}+\cdots+\frac{2 n}{3^{n}}\) is \(\Theta(n)\). Text Transcription: frac 2 n 3+frac 2 n 3^2+frac 2 n 3^3+dots+frac 2 n 3^n Theta(n)

Quantities of the form \(k n+k n \log _{2} n\) for positive integers \(k_{1} \cdot k_{2}\), and n arise in the analysis of the merge sort algorithm in computer science. Show that for any positive integer k, \(k_{1} n+k_{2} n \log _{2} n \text { is } \Theta\left(n \log _{2} n\right)\) . Text Transcription: k n+k n log _2 n k_1 dot k_2 k_1 n+k_2 n log _2 n is Theta(n log _2 n)

Calculate the values of the harmonic sums \(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} \quad \text { for } n=2,3,4, \text { and } 5\). Text Transcription: 1+frac 1 2+frac 1 3+dots+frac 1 n for n=2,3,4, and 5

Use part (d) of Example 11.4 .7 to show that \(n+\frac{n}{2}+\frac{n}{3}+\cdots+\frac{n}{n} \text { is } \Theta(n \ln n)\). Text Transcription: n+frac n 2+frac n 3+dots+frac n n is Theta(n \ln n)

Use the fact that \(\log _{2} x=\left(\frac{1}{\log _{e} 2}\right) \log _{e} x\) and \(\log _{e} x=\) ln x, for all positive numbers x, and part (c) of Example 11.4.7 to show that \(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} \quad \text { is } \quad \Theta\left(\log _{2} n\right)\) Text Transcription: log _2 x=(frac 1 log _e 2) log _e x log _e x= 1+frac 1 2+frac 1 3+dots+frac 1 n is Theta(log _2 n)

a. Show that \(\left\lfloor\log _{2} n\right\rfloor\) is \(\Theta\left(\log _{2} n\right)\). b. Show that \(\left\lfloor\log _{2} n\right\rfloor+1\) is \(\Theta\left(\log _{2} n\right)\). Text Transcription: lfloor log _2 n rfloor Theta(log _2 n) lfloor log _2 n rfloor+1 Theta (log _2 n )

Prove by mathematical induction that \(n \leq 10^{n}\) for all integers \(n \geq 1\). Text Transcription: n leq 10^n n geq 1

Prove by mathematical induction that \(\log _{2} n \leq n\) for all integers \(n \geq 1\). Text Transcription: log _2 n leq n n geq 1

Show that if n is a variable that takes positive integer values, then \(2^{n}\) is O(n!). Text Transcription: 2^n

Let n be a variable that takes positive integer values. a. Show that n! is \(O\left(n^{n}\right)\). b. Use part (a) to show that \(\log _{2}(n !)\) is \(O\left(n \log _{2} n\right)\). c. Show that \(n^{n} \leq(n !)^{2}\) for all integers \(n \geq 2\). d. Use part (c) to show that \(\log _{2}(n !)\) is \(\Omega\left(n \log _{2} n\right)\). e. Use parts (b) and (d) to find an order for \(\log _{2}(n !)\). Text Transcription: O(n^n) log _2(n !) O(n log _2 n) n^n leq(n !)^2 n geq 2 log _2(n !) (n log _2 ) log _2(n !)

a. For all positive real numbers \(u, \log _{2} u<u\). Use this fact to show that for any positive integer \(n, \log _{2} x<n x^{1 / n}\) for all real numbers x > 0. b. Interpret the statement of part (a) using O-notation. Text Transcription: u, log _2 u<u n, log _2 x<n x^1 / n

a. For all real numbers \(x, x<2^{x}\). Use this fact to show that for any positive integer \(n, x^{n}<n^{n} 2^{x}\) for all real numbers x > 0. b. Interpret the statement of part (a) using O-notation. Text Transcription: x, x<2^x n, x^n<n^n 2^x

For all positive real numbers \(u, \log _{2} u<u\). Use this fact and the result of exercise 21 in Section 11.1 to prove the following: For all integers \(n \geq 1, \log _{2} x<x^{1 / n}\) for all real numbers \(x>(2 n)^{2 n}\). Text Transcription: u, \log _2 u<u n geq 1, \log _2 x<x^{1 / n x>(2 n)^2 n

Use the result of exercise 52 above to prove the following: For all integers \(n \geq 1, x^{n}<2^{x}\) for all real numbers \(x>(2 n)^{2 n}\). Text Transcription: n geq 1, x^n<2^x x>(2 n)^2 n

Exercises 54 and 55 use L'Hôpital's rule from calculus. a. Let b be any real number greater than 1. Use L'Hôpital's rule and mathematical induction to prove that for all integers \(n \geq 1\), \(\lim _{x \rightarrow \infty} \frac{x^{n}}{b^{x}}=0\) . b. Use the result of part (a) and the definitions of limit and of O-notation to prove that \(x^{n}\) is \(O\left(b^{x}\right)\) for any integer \(n \geq 1\). Text Transcription: n geq 1 lim _x rightarrow infty frac x^n b^x=0 x^n O(b^x)

Exercises 54 and 55 use L'Hôpital's rule from calculus. a. Let b be any real number greater than 1 . Use L'Hôpital's rule to prove that for all integers \(n \geq 1\), \(\lim _{x \rightarrow \infty} \frac{\log _{b} x}{x^{1 / n}}=0\) . b. Use the result of part (a) and the definitions of limit and of O-notation to prove that \(\log _{b} x\) is \(O\left(x^{1 / n}\right)\) for any integer \(n \geq 1\). Text Transcription: n geq 1 lim _x rightarrow infty frac log _b x x^1 / n=0 log _b x O(x^1 / n) n geq 1

Complete the proof in Example 11.4.4.