Matlab Uch1 Clase7

MATEMÁTICA DISCRETA Clase 7

¿ INDUCCION MATEMATICA ?

•INDUCCIÓN MATEMATICA

1

EL PRINCIPIO DEL BUEN ORDEN Todo conjunto no vacío de enteros positivos posee un mínimo. Esta no es una consecuencia de las reglas aritméticas de N. El principio del buen orden implica que: Dado mєZ, todo subconjunto no vacío de {nєZ / n ≥ m} tiene elemento mínimo. El principio del buen orden es usado para probar la validez de los principios de inducción matemática.

Universidad de Ciencias y Humanidades Algebra Computacional

2

INDUCCIÓN MATEMÁTICA El método de inducción matemática se aplica cuando: 1. sabemos la respuesta al principio. 2. sabemos cómo determinar la respuesta en una etapa a partir de la respuesta en la etapa anterior, y 3. tenemos una expectativa (una idea) de la respuesta general.

Universidad de Ciencias y Humanidades Algebra Computacional

3

En conclusión, el proceso de obtener proposiciones generales de proposiciones particulares se llama inducción. El razonamiento inductivo puede conducir a conclusiones falsas así como verdaderas. Se pondrá en claro este punto mediante dos ejemplos:

Universidad de Ciencias y Humanidades Algebra Computacional

4

Ejemplo1 1)140 es divisible entre 5. 2)Todos los números que terminan en cero son divisibles entre 5. La proposición general (2) obtenida de la particular (1) es verdadera. Ejemplo2 1)140 es divisible entre 5. 2)Todos los números con tres cifras significativas son divisibles entre 5. En este caso la proposición general (2), deducida de la particular (1) es falsa ¿Cómo puede aplicarse la inducción en las matemáticas, de manera que sólo se obtengan proposiciones verdaderas a partir de proposiciones particulares? Universidad de Ciencias y Humanidades Algebra Computacional

5

EJEMPLOS DE INDUCCIÓN ERRONEA Ejemplo 3 Para S n = 1 + 1 + 1 + ... + 1.2

2 .3

3.4

1 n .( n + 1)

Las siguientes igualdades son fáciles de verificar

S1 = S3 =

1 1. 2 1 1. 2

= +

1 2 1 2.3

S2 =

1 1.2

+

1 3.4

=

+

1 2.3

=

2 3

3 4

En base a los resultados anteriores podemos concluir que para todos los números naturales se cumple que:

Sn = Universidad de Ciencias y Humanidades Algebra Computacional

n n +1

¿Verdadero o faso? 6

Ejemplo 4 Para el polinomio

P ( x ) = x 2 + x + 41

si x = 1 tenemos : P (1) = 43 si x = 2 tenemos : P ( 2 ) = 47 si x = 3 tenemos : P ( 3 ) = 53 si x = 4 tenemos : P ( 4 ) = 61 ¿Basándonos en los resultados anteriores podemos decir que para todo entero no negativo x, el valor de P es un número primo?

Universidad de Ciencias y Humanidades Algebra Computacional

7

EL PRINCIPIO DE LA INDUCCIÓN MATEMATICA.Una proposición se cumple para todo número natural n si se satisface las condiciones siguientes: Condición 1: La proposición se cumple para n=1. Condición 2: La veracidad de la proposición para cualquier número natural n=k implica la veracidad para el número siguiente n=k+1.

Universidad de Ciencias y Humanidades Algebra Computacional

8

DEMOSTRACIONES POR INDUCCIÓN MATEMÁTICA Ejemplo1.Halle la suma

1

Sn =

1

+

1.2

+

2.3

1

1

+ ... +

n .( n + 1)

3.4

Solución. Se sabe que

S1 =

1

;

S2 =

2

;

S3 =

3

;

S4 =

4

;

2 3 4 5 Los resultados anteriores nos conducen a la conclusión de que

Sn =

n

n +1

Pero esto se da para los 4 primeros números naturales, probemos que esto se da para todos los números naturales, esto lo haremos mediante la inducción matemática.

Universidad de Ciencias y Humanidades Algebra Computacional

9

Condición 1.- La hipótesis es verdadera para n=1 tal y como se vio anteriormente. Condición 2.- Supóngase que la hipótesis es verdadera para n=k; esto es

Sk =

1 1.2

+

1 2.3

1

+

1

+ ... +

k .( k + 1)

3.4

=

k k +1

Donde k es cualquier número natural. Probemos que a consecuencia, la hipótesis también debe cumplirse para n=k+1, es decir que

S k +1 = Pero

S k +1 = S k +

Universidad de Ciencias y Humanidades Algebra Computacional

k +1

k+2 1

( k + 1)( k + 2 ) 10

De donde sustituyendo el valor de Sk se obtiene

S k +1 = S k +1 =

k

1

+

k +1

( k + 1)( k + 2 )

k +1 k+2

De donde se satisfacen ambas condiciones. De aquí que, a base del principio de inducción matemática , ahora puede afirmarse que para todo número natural n se cumple:

Sn =

Universidad de Ciencias y Humanidades Algebra Computacional

n n +1 11

Ejemplo 2.“Teorema”. Todo número natural es igual al número que le sigue “Demostración” Suponiendo que k=k+1 (1) Probemos que k+1=k+2 (2) En efecto sumando 1 a ambos miembros de la igualdad (1) Se obtiene la igualdad (2). Por lo tanto, si la proposición del teorema es verdadera para n=k , también es verdadera para n=k+1; entonces se ha “ probado el teorema”. ¿Esto es cierto?, ¿En donde se cometió el error? Universidad de Ciencias y Humanidades Algebra Computacional

12

El error consiste en considerar sólo la condición 2 del principio de inducción y no la condición 1. Cada una de las condiciones 1 y 2 tiene su propio significado especial. •La condición 1 proporciona la base para la inducción . •La condición 2 proporciona la justificación para generalizar a partir de esta base, es decir para pasar de n a n+1. Si no se satisface la condición 1 no existe base para aplicar el principio de la inducción matemática

Universidad de Ciencias y Humanidades Algebra Computacional

13

Ejemplo 3.Se sabe que

Sn =

1 1.2

1

+

1

+

2 .3

+ ... +

3.4

1 n .( n + 1)

Supongamos que al hallar la suma obtenemos

n

=

n +1

Sn =

n +1 3n + 1

La fórmula anterior es valida para n=1. Supongamos que se cumple para n=k k +1 Sk = 3k + 1 Debemos llegar a probar que se cumple para n=k+1, es decir S k +1 = Universidad de Ciencias y Humanidades Algebra Computacional

k+2 3k + 4 14

Pero

S k +1 = S k +

1 ( k + 1)( k + 2 )

De donde obtenemos: k +1 1 S k +1 = + 3 k + 1 ( k + 1)( k + 2 )

S k +1 =

k 3 + 4k 2 + 8k + 3 ( k + 1)( k + 2 )( 3 k + 1)

Que no es el resultado esperado. Por lo tanto, la validez de la fórmula para n=k no implica su validez para n=k+1, con lo cual descubrimos que la fórmula

Sk =

k +1 3k + 1

Es falsa. Universidad de Ciencias y Humanidades Algebra Computacional

15

Ejemplo 4.Considere la siguiente función en seudocódigo que calcula el Cuadrado de x. Función cuadrado(x) c=0 d=0 While (d≠x) c=c+x d=d+1 Retornar(c) Probemos que lo anterior es cierto para cualquier valor

Universidad de Ciencias y Humanidades Algebra Computacional

16

Sean cn y dn los valores de c y d luego de pasar n veces por While. Sea P(n) el enunciado: cn=x.dn Se probará por inducción que P(n) es verdadera para todas las n≥1 La condición 1, es c1=x.d1 lo cual es verdad, ya que d1=1 y c1=x La condición 2, supongamos que P(n) es verdadera para n=k, es decir ck=x.dk , debemos probar que ck+1=x.dk+1 Después de pasar una vez mas por While, a c se le suma x y a d se le suma 1. ck+1=ck+x dk+1=dk+1 Entonces ck+1=ck+x =(x.dk)+x=x(dk+1)=x.dk+1 Es decir ck+1=x.dk+1 Por lo cual P(k+1) es verdadera. Por el principio de induccion matemática, se concluye que el ciclo siempre ocurre. Universidad de Ciencias y Humanidades Algebra Computacional

17

Problemas complementarios 1.- Halle la suma de los primeros n números impares Sn=1+3+5+7+…+(2n-1) 2.- Hallar el termino general de la sucesión de números un, donde u1=1 y si para todo número natural k>1 se cumple uk=uk-1+3 Sugerencia: u1=3.1-2 u2=3.2-2 3.- Halle la suma Sn=1+21+22+23+24+…+2n-1 Sugerencia: S1=21-1, S2=22-1 Universidad de Ciencias y Humanidades Algebra Computacional

18

4.- Pruebe que el seudocódigo siempre calcula la diferencia z=x-y subrutina diff(x,y,z) z=x w=y While (w>0) z=z-1 w=w-1 Retornar

Universidad de Ciencias y Humanidades Algebra Computacional

19