Induccion matematica

Matem´tica Discreta a Examen final LADE+ITIG 5 de febrero de 2008 Duraci´n: 3 horas. o El examen est´ compuesto por problemas y se valorar´ sobre 55 puntos. a a La respuesta a cada uno de losproblemas se valorar´ sobre el n´mero de puntos a u indicado. Las respuestas sin justificaci´n se considerar´n como no contestadas. o a No est´ permitido el uso de calculadoras. a Pueden usarse apuntes.Problema 1. (10 puntos) Demostrar por inducci´n que para cada n´mero natural n ≥ 2 o u se tiene que: 1 1 1 13 + + ... + > . n+1 n+2 2n 24 Base de inducci´n: n = 2. El primer miembro de la desigualdad eso 1 1 14 + = 3 4 24 que es en efecto mayor que 13/24. Paso de inducci´n: El primer miembro de la f´rmula para n + 1 es: o o 1 1 1 + + ... + n+2 n+3 2(n + 1) o equivalentemente 1 1 1 1 1 + + ... + + +. n+2 n+3 2n 2n + 1 2n + 2 Por hip´tesis de inducci´n: o o 1 1 1 13 1 + + ... + > − . n+2 n+3 2n 24 n + 1 Por tanto es suficiente probar 13 1 1 1 13 − + + > 24 n + 1 2n + 1 2n + 2 24 o equivalentemente1 1 1 + > . 2n + 1 2n + 2 n+1 1

Haciendo las cuentas tenemos: 4n + 3 1 > (2n + 1)(2n + 2) n+1 o lo que es equivalente (4n + 3)(n + 1) > (2n + 1)(2n + 2). Esta desigualdad es equivalente a n > −1y por tanto cierta. Problema 2. (10 puntos) Una helader´ tiene 14 sabores diferentes de helado (uno de ıa ellos fresa), 4 tipos de crema (una de ellas nata) y 6 complementos (uno de ellos nueces) parahelado. (i) (5 puntos) Si un helado grande tiene 3 bolas de sabores diferentes, 2 cremas diferentes y dos complementos diferentes. Determinar la probabilidad de que un helado grande servido al azartenga una bola de fresa y nueces.
13 2 14 3 4 2 4 2 5 1 6 2

.

(ii) (5 puntos) Si un helado peque˜o tiene 2 bolas de sabores diferentes, 1 crema y n 1 complemento. Determinar la probabilidad deque un helado peque˜o servido al azar n contenga una bola de fresa, no lleve nata y no lleve nueces.
13 1 14 2

×3×5 ×4×6

.

Problema 3. (12 puntos) Sea G = (V, E) un grafo simple. Definimos...