Scribd
Cargar
24 vistas14 páginas

Induccion Matematica-2

Cargado por

fcg.ht.fz
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
24 vistas14 páginas

Induccion Matematica-2

Cargado por

fcg.ht.fz
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

Matemática Discreta

Inducción Matemática

Universidad Mariano Gálvez


Ing. Leonel Arrecis
Agenda
Unidad 3: Inducción Matemática

Definiciones recursivas
Ejercicio – Hoja de Trabajo
Usar el principio de inducción matemática para
demostrar lo siguiente:

Para cualquier n ∈ N,

2 2 2 2
1  3  5  ...(2n  1) 1 / 3n(2n  1)(2n  1)

Resultado final:
Verdadero
Ejercicio – Hoja de Trabajo
Usar el principio de inducción matemática para
demostrar lo siguiente:

Para cualquier n ∈ N,

1* 2  2 * 3  3 * 4  ...n(n  1) [n(n  1)(n  2)] / 3

Resultado final:
Verdadero
Ejercicio – Hoja de Trabajo
Usar el principio de inducción matemática para
demostrar lo siguiente:

Para cualquier n ∈ N,

1/1* 5  1/5 * 9  1 /[(4n  3)(4n  1)] n /( 4n  1)

Resultado final:
Verdadero
Definición Recursiva
La recursividad forma parte del repertorio
para resolver problemas en Computación y es
de los métodos más poderosos y usados.

Los algoritmos recursivos ofrecen soluciones


estructuradas, modulares y elegantemente
simples.
Definición Recursiva
Un razonamiento recursivo tiene dos partes: la base y la
regla recursiva de construcción. La base no es recursiva
y es el punto tanto de partida como de terminación de la
definición.

Un conjunto de objetos está definido recursivamente


siempre que:
 (B) algunos elementos del conjunto se especifican
explícitamente
 (R) el resto de los elementos del conjunto se definen en
términos de los elementos ya definidos

Donde (B) se llama Base y (R) clausula recursiva.


Números de Fibonnaci
Los números de Fibonnaci se definen en forma
recursiva como:
 1) F0 = 0, F1 = 1; y
 2) Fn = Fn-1 + Fn-2, para n∈Z+ con n≥2.

Por lo tanto de la parte recursiva de esta definición


se sigue que:
 F2 = F 1 + F 0 = 1 + 0 = 1
 F3 = F2 + F1 = 1 + 1 = 2
 F4 = F3 + F2 = 2 + 1 = 3
 F5 = F4 + F3 = 3 + 2 = 5
Ejemplo
Considere los siguientes 6 resultados de
operaciones
2 2 2 2
con números de Fibonnaci:
1) F0  F1 0  1 11 Fn x Fn+1
2) F02  F12  F22 0 2  12  12 2 12
3) F02  F12  F22  F32 0 2  12  12  2 2 6 2 3
4) F02  F12  F22  F32  F42 0 2  12  12  2 2  32 15 3 5
5) F02  F12  F22  F32  F42  F52 0 2  12  12  2 2  32  52 40 5 8

n
n  Z 
F
i 0
i
2
Fn Fn 1
Ejemplo
La base de la Inducción, para n=1, nos
demuestra que la conjetura es verdadera
para el primer caso.

Para el paso inductivo suponemos que es


k
verdadera para k≥1, teniendo la hipótesis de
inducción:  2
Fi Fk Fk 1
i 0
k 1


¿Qué ocurre con S(k+1)? Fi
i 0
2
Fk 1 Fk 2
Ejemplo
Resolviendo:
k 1 k

F
i 0
i
2
 Fi  F
i 0
2 2
k 1
k

F
i 0
i
2
F 2
k 1 ( Fk Fk 1 )  F 2
k 1

2
( Fk Fk 1 )  F k 1 Fk 1 ( Fk  Fk 1 )
Ejemplo
Empleando la definición recursiva de los
números de Fibonnaci, reemplazamos F k+Fk+1
por Fk+2
Fk 1 ( Fk  Fk 1 ) Fk 1 Fk 2

Por lo tanto la verdad del caso n = k+1 se


k 1
sigue del caso n = k.
F
i 0
i
2
Fk 1 Fk 2
Hoja de Trabajo
La sucesión de números de Lucas está
estrechamente relacionada con los números
de fibonnaci. Esta sucesión se define de
forma recursiva como sigue:

1) L0 = 2, L1 = 1; y
2) Ln = Ln-1 + Ln-2, para todo n∈Z+ con n≥2

Primeros 12 números de Lucas:


Hoja de Trabajo
Los números de Lucas poseen propiedades
interesantes. Demuestre la siguiente
propiedad: n

L i Ln 2  1
Para n ∈ N, L0 + L1 + L2 + … i+
0 L =
n

También podría gustarte