2018-ELy MD-P3sl - TP 3 principio de induccion PDF

Preview

Summary

TP 3 principio de induccion...

Description

Universidad Nacional de la Patagonia S. J. B.

–

Puerto Madryn

–

2018

Elementos de L´ogica y Matem´atica Discreta Trabajo Pr´actico Nı 3 Principio de Inducci´on - Inducci´on Estructural – RESPUESTAS 3.1. A partir del siguiente diagrama, deducir una f´ ormula para la suma de los n primeros enteros positivos. Demostrarla luego aplicando el principio de induccion. ´

R ESPUESTA : El diagrama sugiere que para n D 6, la suma 1 C 2 C    C 6 D 21 se puede calcular como la mitad de los elementos de un cuadrado de 6  7. Esto da raz o´ n a la siguiente conjetura: 1 C 2 C Cn D

n .n C 1/ 2

otesis se transforme en tesis (de acuerdo al lugar o grado de importancia Ahora, para que nuestra conjetura o hip´ que ocupe en la teor´ıa se le llamar´a proposici´on, corolario, lema, teorema, etc.) debemos demostrarla. En este caso resulta apropiado intentar una demostracion ´ por induccio´ n. 1. Si n D 1, vemos que

1 .1 C 1/ D 1. Es decir, nuestra candidata a f´ ormula “camina” para el caso base. 2

2. Planteamos la hip´otesis inductiva (H. I.). Supongamos que para cierto n D k: 1 C 2 C    C k D k .k C 1/ . 2 3. Ahora, sea n D k C 1, entonces:   k k .k C 1/ .k C 1/.k C 2/ 1C2C k C.k C 1/ D ; C .k C 1/ D .k C 1/ C1 D „ ƒ‚   C … 2 2 2 H.I.

ormula sigue valiendo. lo cual indica que la f´

De 1., 2. y 3. podemos concluir, en virtud del principio de inducci´on, que la f´ormula en v´alida para todo n 2 N . on sigue estos tres pasos (en alguN OTA: Cualquier demostracio´ n en la cual se aplique el principio de inducci´ nos textos los pasos 2. y 3. se resumen en uno). Por razones de espacio vamos a escribir las demostraciones siguientes de manera m´as compacta, pero se recomienda al estudiante aplicado seguir con rigor la metodolog´ıa mostrada en este ejemplo.

1

U. N. P. S. J. B.

–

Elementos de L´ogica y Matem´atica Discreta

–

T.P.Nı 3

–

2018

–

2

3.2. A partir de los siguientes diagramas obtener una f´ormula para las sumas indicadas y demostrarlas luego aplicando el principio de inducci´on.

R ESPUESTA : Sea S.n/ la f´ormula que permite calcular la suma de los primeros n n´ umeros impares consecutivos, a partir de 1, sin tener que sumar t´ ermino a t´ermino (lo que se conoce como la forma cerrada que resuelve el problema). En este ejercicio, la figura de la izquierda muestra que 1 C 3 C 5 C    C 15 D 8  8, esto es S.8/, dado que 15 es el octavo n´umero impar. Esto sugiere la f´ormula: S.n/ W 1 C 3 C    C .2 n  1/ D n2 . Para probar S.n/ por inducci´   on comenzaremos verificando la validez de S.1/, el caso base. Luego probamos on garantiza que S.n/ vale 8n 2 N: Las que 8k S.k/ ! S.k C 1/ y si esto funciona, el principio de inducci´ cuentas son sencillas para este caso, de modo que omitimos los detalles. En la figura de la derecha, con 3 bloques de .1 C 4 C 9 C 16 D 30/ cubos se ha construido un cuerpo que tiene 90 D 4  5  92 cubos. O sea, para n D 4: 30 D 12 C 22 C 32 C 42 D

4  5  .2  4 C 1/ 32

La generalizaci´on de la idea sugerida por la figura lleva a la siguiente ormula: f´ P .n/ W 1 C 22 C    C n2 D

n .n C 1/.2 n C 1/ ; 6

acilmente (hacerlo). Supongamos ahora cuya validez probaremos por inducci´on. P .1/ (el caso base) se verifica f´ que P .k/ es cierta y analicemos P .k C 1/: k .k C 1/.2 k C 1/ C 6 .k C 1/2 k .k C 1/.2 k C 1/ C .k C 1/2 D 6   6  .k C 1/ k .2 k C 1 C 2  2/ C 6 k C 6/ .k C 1/ k .2 k C 1/ C 6 .k C 1/ D D 6 6     .k C 1/ k .2 k C 3/  2 k C 6 k C 6 .k C 1/ k .2 k C 3/ C 4 k C 6 D D 6 6   .k C 1/ k .2 k C 3/ C 2 .2 k C 3/ .k C 1/.k C 2/.2 k C 3/ D D : 6 6

1 C 22 C    C k 2 C .k C 1/2 D

U. N. P. S. J. B.

–

Elementos de L´ogica y Matem´atica Discreta

–

T.P.Nı 3

–

2018

–

3

 Notar queaplicamos la H. I. en el segundo miembro de esta cadena de igualdades. Probamos as´ı que 8k P .k/ ! P .k C 1/ , luego por el principio de inducci´on P .n/ vale 8n 2 N:

3.3. Demostrar que 13 C 23 C    C n3 D .1 C 2 C    C n/2 , para todo n 2 N .

R ESPUESTA : Sea P .n/ W 13 C 23 C    C n3 D .1 C 2 C    C n/2 . 13 D 12 ; as´ı que P .1/ es verdad. Supongamos que P .k/ es verdad, o sea que 13 C 23 C    C k 3 D .1 C 2 C    C k/2 y estudiemos la validez de P .k C 1/ W  2   1 C 2 C    C k C .k C 1/ D 1 C 2 C    C k/2 C 2 .k C 1/ 1 C 2 C    C k/ C .k C 1/2 k .k C 1/ C .k C 1/2 D .13 C 23 C    C k 3 / C 2 .k C 1/ 2 D .13 C 23 C    C k 3 / C k .k C 1/2 C .k C 1/2 D 13 C 23 C    C k 3 C .k C 1/3 :  2 En el segundo miembro desarrollamos el cuadrado del “binomio” .1 C 2 C    C k/ C .k C 1/ , en el tercero ultimo paso “sacamos” .k C 1/2 factor com´un en aplicamos la H. I. y el resultado del ejercicio  3.1 y en el ante´  on que el segundo y tercer t´ermino. Dado que 8k P .k/ ! P .k C 1/ , se concluye por el principio de inducci´ P .n/ vale 8n 2 N. 1 1 1 C  C C , examinando los valores de 23 12 n  .n C 1/ esta expresi´ on para valores peque˜nos de n. Probar luego la f´ormula general aplicando el principio de inducci´on.

3.4. Obtener una f´ormula para la suma

ormula: R ESPUESTA : El c´alculo de los primeros t´erminos de la suma parece indicar la f´ n 1 1 1 D C C C n.n C 1/ 12 23 nC1 Mostramos el paso inductivo: .k C 1/2 1 k .k C 2/ C 1 1 k 1 1 1 D D D C D C C  C C .k C 1/.k C 2/ .k C 1/.k C 2/ k C 1 .k C 1/.k C 2/ k .k C 1/ .k C 1/.k C 2/ 12 23

3.5. Demostrar aplicando el principio de inducci´on: (a) (b) (c) (d) (e)

nŠ < nn para todo entero n mayor que 1. 2n > n2 para todo entero n mayor que 4. n3  n es divisible por 6 para todo entero no negativo n. n2  1 es divisible por 8 para todo entero impar positivo n. 12 C 32 C    C .2n C 1/2 D .n C 1/.2n C 1/.2n C 3/=3 para todo entero n  0.

R ESPUESTA : (a) Paso base: 2Š D 2 < 22 . Si kŠ < k k , entonces: .k C 1/ kŠ D .k C 1/Š < .k C 1/ k k < .k C 1/ .k C 1/k D .k C 1/k+1 : (b) Paso base: 25 D 32 > 52 D 25. Si 2k > k 2 , entonces: 2  2k D 2k+1 > 2  k 2 D k 2 C k 2 > k 2 C 4  k > k 2 C 2  k C 1 D .k C 1/2 : En esta cadena de igualdades/desigualdades usamos la H. I. en el tercer miembro y el hecho de que k > 4 en el quinto.

U. N. P. S. J. B. (c)

–

Elementos de L´ogica y Matem´atica Discreta

–

T.P.Nı 3

–

2018

–

4

Paso base: 03  0 D 0 D 6  0. Si k 3  k D 6  p, donde p 2 N, entonces:

.k C 1/3  .k C 1/ D k 3 C 3  k 2 C 3  k C 1  k  1 D .k 3  k/ C .3  k 2 C 3  k/ D 6  p C 3  k  .k C 1/: Ahora, sabemos que un entero es m´ultiplo de 6 si es m´ultiplo de 2 y 3, simult´aneamente. Si k es par, entonces 3  k  .k C 1/ y por lo tanto el u´ ltimo miembro, es m´ultiplo de 6; si k es impar, luego k C 1 es par y se concluye lo mismo. (d) Paso base: 12  1 D 8  0. Paso inductivo: Dado que todo n´umero impar puede expresarse como 2  n  1, con n 2 Z, la H. I. afirma que .2  k  1/2  1 D 8  r , donde r 2 N , luego:  2  2   2  .k C 1/  1  1 D .2  k  1/ C 2  1 D .2  k  1/2  1 C 4  .2  k  1/ C 4 D 8  r C 8  k D 8  .r C k/: (e) Verificar el paso base para n D 0. Paso Inductivo: Supongamos que 12 C 32 C    C .2 k C 1/2 D .k C 1/.2 k C 1/.2 k C 3/ , entonces: 3

.k C 1/.2 k C 1/.2 k C 3/ .k C 1/.2 k C 1/.2 k C 3/ C C .2 k C 3/2 D 3  3    .2 k C 3/ 2 k 2 C 9 k C 10 .k C 2/.2 k C 3/ 2 k C 5 D : D 3 3

12 C 32 C    C .2 k C 1/2 C .2 k C 3/2 D

Tener en cuenta que las ra´ıces de la ecuaci´on 2 k 2 C 9 k C 10 D 0 son 2 y  25 .

3.6. Sean A y B matrices cuadradas tales que AB D BA (producto de matrices). Demostrar que AB n D B n A para todo entero positivo n. otesis: A B D B A. Supongamos que A B k D B k A, R ESPUESTA : Paso base: para n D 1, tenemos la hip´ luego: A B kC1 D A B k B D B k A B D B k B A D B kC1 A: otesis para obtener el cuarto Notar que hemos aplicado la propiedad asociativa del producto de matrices, la hip´ miembro y, desde luego, la H. I. para el tercero.

3.7. Obtener f .n/, para n  5, si f se define recursivamente de la siguiente manera: (a) (b) (c) (d) (e)

f .0/ D 3, f .n C 1/ D 2f .n/ para n  0. f .0/ D 1, f .1/ D 2; f .n C 1/ D f .n/2 f .n  1/ para n  1. f .0/ D 3, f .n C 1/ D f .n/2  2f .n/  2 para n  0. f .0/ D 3, f .n C 1/ D 3f .n/=3 para n  0. f .0/ D 2, f .1/ D 1; f .n C 1/ D f .n  1/=f .n/ para n  1.

R ESPUESTA : (a) f .0/ D 3; f .1/ D 6; f .2/ D 12; f .3/ D 24; f .4/ D 48; f .5/ D 96. (b) f .1/ D 2; f .2/ D 4; f .3/ D 32; f .4/ D 4096; f .5/ D 536870912: (c) f .0/ D 3; f .1/ D 1; f .2/ D 3; f .3/ D 13; f .4/ D 141; f .5/ D 19597: (d) f .0/ D f .1/ D f .2/ D f .3/ D f .4/ D f .5/ D 3: (e) f .1/ D 1; f .2/ D 2; f .3/ D  12 ; f .4/ D 4; f .5/ D 81:

3.8. Para cada una de las siguientes definiciones recursivas, determinar si es apropiada para definir una funci´on en el conjunto de los enteros no negativos. (a) f .0/ D 0, f .n/ D 2f .n  2/ para n  1. (b) f .0/ D 2, f .1/ D 3; f .n/ D f .n  1/  1 para n  2. (c) f .0/ D 1, f .1/ D 2; f .n/ D 2f .n  2/ para n  2.

U. N. P. S. J. B.

–

Elementos de L´ogica y Matem´atica Discreta

T.P.Nı 3

–

–

2018

–

5

(d) f .0/ D 1, f .1/ D 2; f .3/ D 3, f .n/ D f .n  2/f .n  1/ para n  4. R ESPUESTA : (a) No. (b) S´ı. (c) S´ı.

(d) No, falta la definici´ on de f .2/.

3.9. Para las funciones del ejercicio 3.8 que est´en bien definidas, encontrar una forma expl´ıcita para f .n/, v´alida para todo n  2, y demostrarla por inducci´on. R ESPUESTA : (b) f .n/ D 4  n, para n  2. En efecto, por la definici´ on recursiva de f vemos que f .2/ D f .1/  1 D 2 D 4  2. Esto muestra la validez del paso base. Supongamos ahora que f .k/ D 4  k, luego f .k C 1/ D f .k/  1 D 4  .k C 1/. (c) Recordemos la funci´on Œx W “Parte entera de x”, definida para todo x 2 R como el mayor n´ umero entero menor o igual que x: Por ejemplo: Œ2;1 D Œ2;99 D Œ2 D 2, Œ3;73 D Œ4 D 4, Œ D 3, etc. La ıcita como: funci´on definida en este ejercicio puede escribirse en forma expl´ f .n/ D 2Œ

nC1 2

 ; 8n  2:

2C1 Definici´on que mostramos por inducci´on. Paso base: f .2/ D 2  f .0/ D 2 D 2Œ 2  . Paso de inducci´on: Si k f .k  1/ D 2Œ 2  , entonces:

f .k C 1/ D 2  f .k  1/ D 2  2Œ 2  D 21CŒ2  D 2Œ1C 2  D 2Œ k

k

k

kC2 2

:

3.10. Dar una definici´on recursiva para la funci´on f .n/, n 2 N, en cada uno de los siguientes casos: (a) (b) (c) (d) (e)

f .n/ D 6n. f .n/ D 10n . f .n/ D 1 C .1/n . f .n/ D 2n C 1: f .n/ D n2 .

R ESPUESTA : (a) f .1/ D 6; f .n/ D f .n  1/ C 6 8n  2. (b) f .1/ D 10; f .n/ D 10  f .n  1/ 8n  2. (c) f .1/ D 0; f .n/ D f .n  1/ C 2  .1/n 8n  2. (d) f .1/ D 1; f .n/ D f .n  1/ C 2  n  1 8n  2. on. Por ejemplo, en (c) podr´ıamos haber escrito: N OTA: Existen varias formas de expresar cada funci´ ( f .n  1/ C 2 si n es par. f .n/ D f .n  1/  2 si n es impar.

3.11. Considerar la siguiente funci´on f .n/ definida recursivamente: f .0/ D 1; f .n/ D f .n  1/ C 3; para n  1: (a) Obtener f .n/, para n  5. (b) Encontrar una forma expl´ıcita para f .n/, v´alida para todo n, y demostrarla por inducci´on. R ESPUESTA : (a) f .0/ D 1; f .1/ D 4; f .2/ D 7; f .3/ D 10; f .4/ D 13; f .5/ D 16. ´ : f .0/ D 1 D 3  0 C 1. Si f .k/ D 3  k C 1, entonces: (b) C ONJETURA : f .n/ D 3  n C 1. D EMOSTRACION f .k C 1/ D f .k/ C 3 D 3  .k C 1/ C 1:

U. N. P. S. J. B.

–

Elementos de L´ogica y Matem´atica Discreta

–

T.P.Nı 3

–

2018

–

6

on f .n/ definida recursivamente: 3.12. Repetir el ejercicio anterior 3.11 para la funci´ f .0/ D 2; f .n/ D 3:f .n  1/; para n  1: R ESPUESTA : (a) f .0/ D 2; f .1/ D 6; f .2/ D 18; f .3/ D 54; f .4/ D 162; f .5/ D 486. ´ : f .0/ D 2 D 2  30 . Si f .k/ D 2  3k , entonces: (b) C ONJETURA : f .n/ D 2  3n . D EMOSTRACI ON f .k C 1/ D 3  f .k/ D 3  2  3k D 2  3kC1 :

3.13. Dar una definici´on recursiva de: (a) El conjunto de los enteros pares. (b) El conjunto de los enteros no divisibles por 3. R ESPUESTA : (a) Sea P el conjunto de los enteros pares. Luego 0 2 P y si p 2 P , entonces .p C 2 2 P / ^ .p  2 2 P /. (b) Sea S D fx W x no es divisible por 3g  Z. Luego .1 2 S/ ^ .2 2 S / y si x 2 S , entonces .x C 3 2 S / ^ .x  3 2 S /.

3.14. Sea S el subconjunto de pares ordenados de n´umeros enteros definido recursivamente del siguiente modo: 1. .0; 0/ 2 S . 2. Si .a; b/ 2 S , entonces .a C 2; b C 3/ 2 S y .a C 3; b C 2/ 2 S . (a) Enumerar los elementos de S obtenidos por las primeras cinco aplicaciones de la regla recursiva. on para probar que a C b es m´ ultiplo de 5 para todo .a; b/ 2 S . (b) Utilizar el principio de inducci´ R ESPUESTA : (a) S =f.0; 0/; .2; 3/; .3; 2/; .4; 6/; .5; 5/; .6; 4/; .6; 9/; .7; 8/; .8; 7/; .8; 12/; .9; 6/; .9; 11/; .10; 10/; .10; 15/; .11; 9/; .11; 14/; .12; 8/; .12; 13/; .13; 12/; : : : g. (b) N OTA: Empleamos aqu´ı el s´ımbolo “ j ” que representa la relaci´ on “divide a”. Por ejemplo a j b se lee: “a divide a b”, o tambi´en “b es m´ultiplo de a”. ´ : .0; 0/ 2 S y 5 j .0 C 0/, as´ı que se verifica el paso base. Ahora, suponiendo que .a; b/ 2 S D EMOSTRACION y 5 j .a C b/ se sigue de la definici´on recursiva de S que .a C 2; b C 3/ 2 S y es claro que 5 j .a C b C 3 C 2/.

3.15. Sea † D f0; 1g; †es el conjunto de las cadenas binarias. Recordar la definici´on recursiva de †: 1. La cadena nula  2 † . 2. Si ! 2 † , entonces !0 2 † y !1 2 † . as que la cadena (a) Mostrar que si ! 2 † entonces la cadena 01 aparece en ! a lo sumo una vez m´ 10. (b) Dar una definici´ on recursiva de la funci´on unos.!/ que devuelve el n´umero de unos de la cadena !. on para probar que (c) Sea ˛ 2 † , utilizar el principio de inducci´ unos.˛!/ D unos.˛/ C unos.!/, para todo ! 2 † . (d) Dar una definici´ on recursiva de la funci´ on i nve rsa.!/ que devuelve la cadena que tiene los s´ımbolos de ! dispuestos en orden inverso.

U. N. P. S. J. B.

–

Elementos de L´ogica y Matem´atica Discreta

–

T.P.Nı 3

–

2018

–

7

R ESPUESTA : (a) Sea la cadena de bits ! 2 † . La proposici´on P .!/ W “La cadena 01 aparece en ! a lo sumo una vez m´as que la cadena 10” es trivialmente verdadera si ! D . Si ! es no vac´ıa, se puede escribir ! D ck uk ck1 uk1    c1 u1 , donde ci y ui (con 1  i  k y k 2 N) representan cada “subcadena” de ceros y unos en !, respectivamente. Podemos suponer ui ¤  para 2  i  k y ci ¤  para 1  i  k  1, as´ı, si u1 D , entonces ! termina en 0 y si ck D  es porque ! comienza con 1. Lo que var´ıa en cada !, desde luego, es k , long.ci / y long.ui /. Razonando as´ı s´olo resta considerar los distintos casos: 1. Si ck D u1 D , entonces la cadena “10” aparece k  1 veces y “01” k  2 veces. 2. Si ck D  ¤ u1 , “10” y “01” aparecen k  1 veces. 3. Si u1 D  ¤ ck , “10” y “01” aparecen k  1 veces. 4. Si ck ¤  y u1 ¤ , “10” aparece k  1 veces y “01” k veces. Esto muestra que P .!/ es verdadera para toda ! 2 † . on: N OTA: Veamos algunos ejemplos de cada caso, a fin de ilustrar el razonamiento seguido para la demostraci´ C ASO 1: ! D 10, k D 2, long.c1 / D long.u2 / D 1. ! D 10100010, k D 4, long.c1 / D long.c3 / D long.u2 / D long.u3 / D long.u4 / D 1, long.c2 / D 3. C ASO 2: ! D 1, k D 1, long.u1 / D 1. ! D 101, k D 2, long.u1 / D long.u2 / D long.c1 / D 1. ! D 11100001, k D 3, long.c1 / D 4, long.u1 / D 1, long.u2 / D 3. C ASO 3: ! D 0, k D 1, long.c1 / D 1. ! D 00010, k D 2, long.c1 / D long.u2 / D 1, long.c2 / D 3. ! D 011000100, k D 3, long.c1 / D long.u3 / D 2, long.u2 / D 1, long.c3 / D 1. C ASO 4: ! D 01, k D 1, long.c1 / D long.u1 / D 1. ! D 000101, k D 2, long.u1 / D long.u2 / D long.c1 / D 1, long.c2 / D 3. ! D 011000101, k D 3, long.u1 / D long.c1 / D long.u2 / D long.c3 / D 1, long.c2 / D 3, long.u3 / D 2. on recursiva, sea !x 2 † una cadena donde ! 2 † y x 2 †, (b) Sea unos./ D 0. Para la definici´ entonces: ( unos.!/ si x D 0 unos.!x/ D 1 C unos.!/ si x D 1 (c) Sean ˛; ! 2 † . Aplicaremos el principio de inducci´on sobre unos.!/. PASO BASE : si ! D , entonces unos.!/ D 0 y es trivial que unos.˛!/ D unos.˛/ C unos.!/. PASO I NDUCTIVO: Supongamos ahora que on dada unos.˛!/ D unos.˛/ C unos.!/ y sea x 2 † (esto es, x D 0 ˚ x D 1), entonces aplicando la definici´ en el inciso anterior resulta: ( unos.˛!/ si x D 0 unos.˛!x/ D 1 C unos.˛!/ si x D 1 y en cualquier caso se verifica unos.˛!x/ D unos.˛/ C unos.!x/. (d) Sea inversa./ D . Consideremos ahora la cadena de bits !x , donde ! 2 † y x 2 †, entonces: inversa.!x/ D x inversa.!/:...