Existe un entero n tal que r n. Caso 1 (r 0): En este caso, tomamos n 1. Entonces r n. Caso 2 (r 0): En esta situación, r = a b para algunos e...

Existe un entero n tal que r n. Caso 1 (r 0): En este caso, tomamos n 1. Entonces r n. Caso 2 (r 0): En esta situación, r = a b para algunos enteros positivos a y b (por definición de racional y porque r es positivo). Observe que r = a b < n si y sólo si, a nb. Sea n 2a. Multiplicamos ambos lados de la desigualdad 1 2 por a para obtener a 2a y multiplicamos ambos lados de la desigualdad 1 b por 2a para obtener que 2a 2ab nb. Así a 2a nb, entonces, por transitividad de orden, a nb. Dividiendo ambos lados entre b se tiene que a b < n o, equivalentemente, que r n. En consecuencia, en ambos casos, r n [que era lo que se quería demostrar]. 23. Sugerencia: Si r es cualquier número racional, sea S el conjunto de todos los enteros n tales que r n. Use los resultados de los ejercicios 22a), 22c) y el principio del buen orden para los enteros, para demostrar que S tiene un elemento mínimo, digamos y entonces demostrar que ฀ 1 r . 24. Demostración: Sea S el conjunto de todos los enteros r tales que n 2i r para algún entero i. Entonces n S porque n 20 n y así S = . También, como n 1, cada r en S es positivo y además, por el principio del buen orden, S tiene un elemento mínimo m. Esto significa que n 2k m (*) para algún entero k no-negativo y m r para cada r en S. Afirmamos que m es impar. La razón es que si m fuera par, entonces m 2p para algún entero p. Sustituyendo en la ecuación (*) resulta: n 2k m 2k 2p (2k 2)p 2k 1 p. 5.4 Soluciones y sugerencias para los ejercicios seleccionados A-39 A-40 Apéndice B Soluciones y sugerencias para los ejercicios seleccionados Se tiene que p S y p m, que contradice el hecho de que m es el elemento mínimo de S. Así que m es impar y entonces n m 2k para algún entero impar m y un entero k no-negativo. 29. Sugerencia: En el paso inductivo, divida en casos dependiendo de si k se puede escribir como k 3x o k 3x 1 o k 3x 2 para algún entero x. 30. Sugerencia: En el paso inductivo, sea k 0 un entero dado y supongamos que existen enteros q y r tales que k dq r y 0 r d. Debe demostrar que existen enteros q y r tales que: k 1 dq r y 0 r d. Al hacer esto, considera los casos r d ฀ 1 y r d ฀ 1. 31. Sugerencia: Dado un predicado P(n) que satisface las condiciones (1) y (2) del principio de inducción matemática, sea S el conjunto de todos los enteros mayores o iguales a a para que P(n) es falso. Suponga que S tiene uno o más elementos y use el principio del buen orden para deducir una contradicción. 32. Sugerencia: Suponga que S es un conjunto que contiene uno o más enteros, todos mayores o iguales que algún entero a y suponga que S no tiene un elemento mínimo. Deje que la propiedad P(n) sea la frase “i no es elemento de S para cualquier entero i con a i n”. Use inducción matemática para demostrar que P(n) es verdadero para todos los enteros n a y explique cómo este resultado contradice la suposición de que S no tiene un elemento mínimo. Sección 5.5 1. Demostración: Suponga que el predicado m n 100 es verdadero antes de entrar al bucle. Entonces mantiguo nantiguo 100. Después de la ejecución del bucle, mnuevo mantiguo 1 y nnuevo nantiguo ฀ 1, así mnuevo nnuevo (mantiguo 1) (nantiguo ฀ 1) mantiguo nantiguo 100. 3. Demostración: Suponga que el predicado m3 n2 es verdadero antes de la entrada al bucle. Entonces mantiguo 3 nantiguo 2. Después de la ejecución del bucle, mnuevo 3 mantiguo y nnuevo 5 nantiguo , así m3 nuevo 3 mantiguo 3 27 m3 antiguo 27 n2 antiguo Pero como nnuevo 5 nantiguo, entonces nantiguo 1 5 nnuevo. Por tanto m3 nuevo 27 n2 antiguo 27 1 5 nnuevo 2 27 1 25 n2 nuevo 27 25 n2 nuevo n2 nuevo 27 25 n2 nuevo n2 nuevo