Demostración de que P(1) es verdadera: Cuando n 1, la desigualdad es 1 10, que es verdadera. Demostración que para todos los enteros k 1, si P(k...

Demostración de que P(1) es verdadera: Cuando n 1, la desigualdad es 1 10, que es verdadera. Demostración que para todos los enteros k 1, si P(k) es verdadera, entonces P(k 1) también es verdadera. Sea k cualquier entero con k 1 y suponga k 10k. [Esta es la hipótesis de inducción.] Debemos demostrar que k 1 10k 1. Por hipótesis de inducción, k 10k. Sumando 1 en ambos lados se obtiene k 1 10k 1. Pero cuando g 10k + 1 ≤ 10k + 9 ·10k = 10 ·10k = 10k+1. Así, por transi- tividad de orden, k 1 10k 1 [que era lo que se quería demostrar]. 47. Sugerencia: Para demostrar el paso inductivo, use el hecho de que si k 1, entonces k 1 2k. Aplique la función logarítmica de base 2 en ambos lados de esta desigualdad y utilice propiedades de los logaritmos. 48. Sugerencia: 2 2 2 2 2 2 3 4 n 2 n n factores 49. a. Demostración: Suponga que n es una variable que tome valores enteros positivos. Entonces n! n (n ฀ 1) (n ฀ 2) . . . 2 1 n factores n n n n . . . n nn n factores 1, las propiedades de los logaritmos y de los exponentes (vea la sección 7.2) implica que 0 log2 x log2 x1 n n n log2 x1 n nx1 n donde la última desigualdad se satisface sustituyendo x1 n en lugar de u en log2 u u. b. Sea B n y b 1. Entonces x x0 log2 x log2 x B x1 n y por lo tanto log2 x es O(x1 n). 52. Sea n un entero positivo y suponga que x (2n)2n. Por las propiedades de los logaritmos, log2 x 2n 1 2n log2 x 2n log2 x 1 2n 2nx 1 2n (*) (donde la última desigualdad vale sustituyendo x 1 2n en lugar de u en log2u u). Pero elevando ambos lados de x (2n)2n a la potencia 1 2 se obtiene x1/2 > ((2n)2n)1/2 = (2n)n . Cuando se multiplican ambos lados por x1/2, el resultado es x = x1/2x1/2 > x1/2(2n)n = x1/2(2n)n, o de un modo más compacto, x1/2(2n)n < x . Entonces, ya que la función potencia se define por x x1 n está creciendo para toda x 0 (vea el ejercicio 21 de la sección 11.1), podemos tomar la raíz enésima en ambos lados de la desigualdad y usando las leyes de los exponentes obtenemos x1 2 2n n 1 n x1 n O, equivalentemente, 2nx 1 2n x1 n .(**) Ahora use la transitividad del orden (apéndice A, T18) para combinar (*) y (**) y concluir que log2 x x1 n [que era lo que se quería demostrar]. 54. Demostración (por inducción matemática): Sea b un número real con b 1 y sea la propiedad P(n) la ecuación lím x xn bx 0 Demostración de que P(1) es verdadera: Por la regla de L’Hôpital, límx x1 bx límx 1 bx ln b 0. Así P(1) es verdadera. Demostración que para todos los enteros k 1, si P(k) es verdadera, entonces P(k 1) también es verdadera. Sea k cualquier entero con k 1 y suponga que límx xk bx 0. [Esta es la hipótesis de inducción.] Debemos demostrar que límx xk 1 bx 0 Pero por la regla de L’Hôpital, límx xk 1 bx límx k 1 xk ln b bx k 1 ln b límx xk bx k 1 ln b 0 [por la hi- pótesis de inducción] 0. [Que era lo que se quería demostrar.] b. Por el resultado del inciso a) y por la definición de límite dado cualquier número real 0, existe un entero N tal que | xn bn − 0| < ε para toda x N. En este caso tome 1. Se tiene que para toda x > N , | xn bx | = | xn bx | < 1. Multiplicando ambos lados por bx , para obtener xn bx . Sea B 1 y b N. Entonces |xn| < B · |bx | para toda x b. Así por definición de la O-notación, xn es O(bx). Sección 11.5 3. log2 1000 = log2(103) = 3 log2 10 ∼= 3(3.32) ∼= 9.96 log2(1,000,000) = log2(106) = 6 log2 10 ∼= 6(3.32) ∼= 19.92 log2(1,000,000,000,000) = log2(1012) = 12 log2 10 ∼= 12(3.32) = 39.84 2. a. Si m 2k, donde k es un entero positivo, entonces el algo- ritmo requiere de c⌊log2(2 k)⌋ = c⌊k⌋ = ck operaciones. Si el tamaño de entrada es m2 (2k)2 22k, entonces el número de operaciones requerido es c⌊log2(2 2k)⌋ = c⌊2k⌋ = 2(ck). Que es el número de operaciones dobles. b. Como en el inciso a), para una entrada de tamaño m 2k, donde k es un entero positivo, el algoritmo requiere ck operaciones. Si se incrementa el tamaño de entrada a m10 (2k)10 210k, entonces el número de operaciones requeridas es c⌊log2(2 10k)⌋ = c⌊10k⌋ = 10(ck). Así el número de ope- raciones aumenta en un factor de 10. c. Cuando el tamaño de entrada aumenta de 27 a 228, el factor con el que el número de operaciones aumenta es c⌊log2(2 28)⌋ c⌊log2(2 7)⌋ = 28c 7c = 4. 3. Una pequeña exploración numérica puede ayudar para encontrar una ventana inicial para dibujar las gráficas de y x y de y [50 log2 x]. Observe que x = 28 = 256, ⌊ 50 log2 x ⌋ = ⌊ 50 log2 (28) ⌋ ⌊50 ·8⌋ ⌊400⌋ ⌊ 400 256 x. Pero cuando x = 29 = 512, ⌊ 50 log2 x ⌋ = ⌊ 50 log2(2 9) ⌋ ⌊50 ·9⌋ ⌊450⌋ = 450 512 x. Así una buena elección de una ventana inicial sería el intervalo de 256 a 512. Dibujando las gráficas , acerque si es necesario y al usar la característica de trazo se encuentra que cuando < 438, n < ⌊ 50 log2 n ⌋. 5. a. índice 0 1 inf 1 superior 10 4 1 medio 5 2 1 11.5 Soluciones y sugerencias para los ejercicios seleccionados A-117 A-118 Apéndice B Soluciones y sugerencias para los ejercicios seleccionados b. índice 0 inf 1 6 7 superior 10 7 6 medio 5 8 6 7 7. a. superior ฀ inf 1 b. Demostración: Suponga que superior e inf son enteros positi- vos dados tales que superior ฀ inf 1 es un número impar. Entonces, por definición de impar, hay un entero k tal que superior ฀ inf 1 2k 1 Sumando 2 inf ฀ 1 a ambos lados se obtiene inf superior 2 inf ฀ 1 2k 1 2(inf k). Pero inf k es un entero. Por lo tanto, por definición de par inf superior. 8. n 27 13 6 3 1 0 9. Para cada entero positivo, n, n div 2 = ⌊n/2⌋. Así cuando el segmento del algoritmo se ejecuta para una n particular y el bucle while ha iterado una vez, la entrada de la siguiente iteración es n 2 . Se tiene que el número de iteraciones del bucle para n es uno más que el número de iteraciones