ÁLGEBRA Y MATEMÁTICAS DISCRETAS.
TEMA 2.
INDUCCIÓN Y RECURSIÓN.
Docente: MCI. Vanessa del Rosario Alcalá Ramírez.
UNIR MÉXICO
Bienvenida de los Profesores
Convocatoria Septiembre 2022
/
¿CÓMO ESTUDIAR ESTE TEMA?
➢ Para estudiar este tema lee:
➢ Números naturales y recursividad.
➢ Lee los apartados 3.3 y 3.4 del capítulo 3 «Razonamiento matemático,
inducción y recursividad» (páginas 222-255) del manual de la
asignatura: Matemática discreta y sus aplicaciones de Kenneth Rosen.
Disponible en la Biblioteca Virtual de UNIR.
Universidad Internacional de La Rioja en México 2
INTRODUCCIÓN.
La inducción matemática se usa para demostrar
resultados sobre una gran variedad de objetos distintos.
Por ejemplo, se emplea para demostrar propiedades
acerca de la complejidad de los algoritmos, estudiar si son
correctos ciertos tipos de programas de ordenador o
teoremas sobre grafos y árboles, asó como un amplio
abanico de identidades y desigualdades.
Universidad Internacional de La Rioja en México 3
INTRODUCCIÓN.
Es importante dejar claro que la inducción matemática solo
se puede aplicar en la demostración de resultados que se
han obtenido de alguna otra forma. No es una herramienta
para descubrir fórmulas o teoremas.
Universidad Internacional de La Rioja en México 4
INTRODUCCIÓN.
Existen varios ejemplos de inducción matemática. Uno de
ellos tiene que ver con un grupo de personas formando
una cola. Alguien le susurra un secreto al oído a la primer
persona de la cola, y cada persona le cuenta el secreto a
la siguiente persona de la cola inmediatamente después
de escucharlo.
Sea P(n) la proposición que afirma que la persona n
conoce el secreto. Entonces, P(1) es verdadera, puesto
que alguien le ha contado el secreto a la primera persona
de la cola; P(2) es verdadera, pues la primer persona
reveló el secreto a la segunda; P(3) es verdadera porque
la segunda persona le cuenta el secreto a la tercera y así
sucesivamente.
Universidad Internacional de La Rioja en México 5
INTRODUCCIÓN.
Para esto, se asume que cada
persona transmite el
secreto sin modificarlo, lo cual
no es cierto en la vida real.
Universidad Internacional de La Rioja en México 6
INTRODUCCIÓN.
Otro ejemplo es considerar una fila
infinita de fichas de dominó colocadas
de pie, etiquetadas con los números
1,2,3,..., n. Sea P(n) la proposición que
afirma que la ficha n se car. Si cae la
primera ficha, es decir, si P(1) es
verdadera, y si siempre que la ficha n
se caiga también se cae la (n+1), es
decir si P(n) → P(n+1) es verdadera,
entonces se caeran todas las fichas.
Universidad Internacional de La Rioja en México 7
INDUCCIÓN MATEMÁTICA.
Universidad Internacional de La Rioja en México 8
INDUCCIÓN MATEMÁTICA.
Universidad Internacional de La Rioja en México 9
INDUCCIÓN MATEMÁTICA.
Lo primero que se hace para demostrar que P(n) es verdadera
para todo entero positivo n es mostrar que P(1) es verdadera.
Esto no es más que mostrar que la sentencia particular obtenida
al sustituis n por 1 en P(n) es verdadera.
Posteriormente, tenemos que demostrar que P(k) → P(k+1) es
verdadera para todo entero positivo k. Para demostrar que esta
implicación es verdadera para todo entero positivo k,
necesitamos mostrar que P(k+1) no puede ser falsa cuando P(k)
es verdadera. Esto se puede hacer suponiendo que P(k) es
verdadera y mostrando que bajo esta hipótesis P(k+1) debe de
ser también verdadera.
Universidad Internacional de La Rioja en México 10
INDUCCIÓN MATEMÁTICA.
EJEMPLO.
Utiliza el método de inducción matemática para demostrar que la
suma de lo n primeros enteros positivos impares es n2
Solución: Sea P(n) la proposición que afirma que la suma de los
n primeros enteros positivos impares es n2 .
En primer lugar, debemos completar el caso base:
• Tenemos que verificar que P(1) es verdadera.
Después llevaremos a cabo el paso de inducción, esto es,
debemos de mostrar que P(k+1) es verdadera cuando se supone
que P(k) es verdadera.
Universidad Internacional de La Rioja en México 11
INDUCCIÓN MATEMÁTICA.
EJEMPLO.
PASO BASE: P(1) afirma que la suma del primer entero impar es
12 . Esto es cierto, puesto que el primer entero positivo impar es
1.
PASO DE INDUCCIÓN: Para completar el paso de inducción
debemos demostrar que la proposición P(k) → P(k+1) es
verdadera para todo entero positivo k. Para hacer esto, vamos a
suponer que P(k) es verdadera para un entero positivo k, esto es,
1 + 3 + 5 + ... + (2k-1) = k2
Universidad Internacional de La Rioja en México 12
INDUCCIÓN MATEMÁTICA.
EJEMPLO.
1 + 3 + 5 + ... + (2k-1) = k2
(El k-ésimo entero positivo impar es (2k-1), ya que este entero se
obtiene sumando 2 un total de k-1 veces a 1).
Debemos demostar que P(k+1) es verdadera suponiendo que
P(k) es verdadera. Hay que tener en cuenta que P(k+1) es la
sentencia que afirma que
1 + 3 + 5 +...+ (2k-1)+(2k+1) = (k+1) 2
Universidad Internacional de La Rioja en México 13
INDUCCIÓN MATEMÁTICA.
EJEMPLO.
1 + 3 + 5 +...+ (2k-1)+(2k+1) = (k+1) 2
k2
k2 + 2k + 1 = (k+1) 2
DEMOSTRACIÓN POR INDUCCIÓN.
Esto muestra que P(k) → P(k+1). Observa que hemos usado la hipótesis de
inducción P(k) en la segunda igualdad para reemplazar la suma de los
primeros k enteros positivos impares por k2
Puesto que P(1) es verdadera y que P(k) → P(k+1) también lo es para todo
entero positivo k, el princiío de inducción matemática muestra que P(n) es
verdadera para todo entero positivo n.
Universidad Internacional de La Rioja en México 14
INDUCCIÓN FUERTE.
Universidad Internacional de La Rioja en México 15
INDUCCIÓN FUERTE.
Universidad Internacional de La Rioja en México 16
PROPIEDAD DEL BUEN ORDEN
Universidad Internacional de La Rioja en México 17
POR QUÉ ES VÁIDA LA INDUCCIÓN MATEMÁTICA
La razón proviene de la propiedad del buen orden. Supongamos
que conocemos que P(1) es verdadera y que también lo es la
proposición P(k) → P(k+1) para todos los enteros positivos k.
Para demostrar que P(n) debe de ser verdadera para todo entero
positivo suponemos que hay al menos un entero positivo para el
cual P(n) es falso. Entonces, el conjunto S de los enteros
positivos n para los que P(n) es falsa, es no vacío. Por lo tanto,
por la propiedad del buen orden, S tiene un elemento mínimo,
que se puede denotar por m. Sabemos que m no puede ser 1,
puesto que P(1) es verdadera.
Universidad Internacional de La Rioja en México 18
POR QUÉ ES VÁIDA LA INDUCCIÓN MATEMÁTICA
Como m es positivo y mayor que 1, m -1 es un entero positivo.
Además, como m-1 es menor que m no está en S, por lo que
P(m-1) debe de ser verdadera. Como la implicación P(m-1) →
P(m) es también verdadera,, se debe cumplir que P(m) es
verdadera. Esto contradice la elección de m. Así, P(n) debe ser
verdadera para todo entero n positivo.
Universidad Internacional de La Rioja en México 19
RECURSIVIDAD
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.
La recursividad es un concepto fundamental en matemáticas y en computación.
Una definición recursiva dice cómo obtener conceptos nuevos empleando el
mismo concepto que intenta describir.
En toda situación en la cual la respuesta pueda ser expresada como una
secuencia de movimientos, pasos o transformaciones gobernadas por un
conjunto de reglas no ambiguas, la fórmula recursiva es un buen candidado para
resolver el problema.
Universidad Internacional de La Rioja en México 20
RECURSIVIDAD
Las definiciones recursivas de funciones en matemáticas que tienen como
argumentos números enteros, se llaman relaciones de recurrencia.
Forma de una ecuación de recurrencia:
coar +c1ar-1 + c2ar-2 + ....+ ckar-k = f(r) función matemática discreta
donde ci son constantes, es llamada una ecuación de recurrencia de coeficientes
constantes de orden k, condicionada a que c0 y ck = 0.
Una definición recursiva dice cómo obtener conceptos nuevos empleando el
mismo concepto que intenta definir.
Universidad Internacional de La Rioja en México 21
RECURSIVIDAD
El poder de la recursividad es que los procedimientos o conceptos complejos
pueden expresarse de una forma simple.
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.
Base: La secuenciación, iteración condicional y selección son estructuras válidas
de control que pueden ser consideradas como enunciados.
Regla recursiva: Las estructuras de control que se pueden formar combinando
de manera válida la secuenciación iteración condicional y selección también son
válidos.
Universidad Internacional de La Rioja en México 22
RECURSIVIDAD
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
(R) se llama cláusula recursiva
Observaciones:
1. El procedimiento se llama a si mismo
2. El problema se resuelve, resolviendo el mismo problema pero de tamaño
menor
3. La manera en la cual el tamaño del problema disminuye asegura que el caso
base eventualmente se alcanzará
Universidad Internacional de La Rioja en México 23
RECURSIVIDAD
La recursividad es un método poderoso usado en inteligencia artificial, su poder
es que algunos conceptos complejos pueden expresarse en una forma simple.
Una definición recursiva difiere de una definición circular en que tiene una forma
de escapar de su expansión infinita. Este escape se encuentra en la definición o
porción no recursiva o terminal de la definición.
Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de
teoremas, solución de problemas combinatorios, algunos acertijos, etc.
Universidad Internacional de La Rioja en México 24
DEFINICIONES RECURSIVAS
Universidad Internacional de La Rioja en México 25
FUNCIONES DEFINIDAS RECURSIVAMENTE
Universidad Internacional de La Rioja en México 26
FUNCIONES DEFINIDAS RECURSIVAMENTE
Universidad Internacional de La Rioja en México 27
INDUCCIÓN ESTRUCTURAL
La inducción estructural es útil aplicarla para demostrar un
resultado sobre un conjunto definido recursivamente.
Este tipo de inducción consta de dos partes:
Universidad Internacional de La Rioja en México 28
INDUCCIÓN GENERALIZADA
La inducción generalizada se aplica a conjuntos que
cumplen con la propiedad de buena ordenación, además
de los conjuntos de enteros, es decir, a conjuntos no
formados por elementos simples individuales.
Universidad Internacional de La Rioja en México 29
INDUCCIÓN.
EJERCICIO.
Utiliza el método de inducción para demostrar la desigualdad
n < 2n
Solución: Sea P(n) la proposición n < 2n
Universidad Internacional de La Rioja en México 30
INDUCCIÓN FUERTE.
EJERCICIO.
Muestra que si n es un entero mayor que 1, entonces n se puede
escribir como el producto de números primos.
Solución: Sea P(n) la proposición que afirma que n se puede
escribir como producto de números primos.
Universidad Internacional de La Rioja en México 31
RECURSIVIDAD
EJERCICIO.
* Da una definición recursiva de la función factorial F(n) = n!
* Obtener los números de la serie de fibonacci f2, f3, f4, f5, f6
Universidad Internacional de La Rioja en México 32
