MATEMÁTICAS DISCRETAS

Guı́a de Estudio - Semana 2

Inducción Matemática, Inducción Fuerte y Definiciones Recursivas

Índice
1. Introducción: ¿Por qué aprender inducción? 3
1.1. El problema fundamental . . . . . . . . . . . . . . . . . . . 3
1.2. La analogı́a del dominó . . . . . . . . . . . . . . . . . . . . 3

2. Inducción Simple (Primer Principio) 4

2.1. Definición formal . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Estructura de una demostración por inducción . . . . . . . 5
2.3. Ejemplo 1: Suma de los primeros n naturales . . . . . . . . 6
2.4. Ejemplo 2: Suma de los primeros n impares . . . . . . . . 7
2.5. Ejemplo 3: Desigualdad (útil en análisis de algoritmos) . . 8
2.6. Ejemplo 4: Divisibilidad . . . . . . . . . . . . . . . . . . . 9

3. Inducción Fuerte (Segundo Principio) 9

3.1. ¿Cuándo necesitamos inducción fuerte? . . . . . . . . . . . 9
3.2. Definición formal . . . . . . . . . . . . . . . . . . . . . . . 10
3.3. Ejemplo 5: Sucesión de Fibonacci . . . . . . . . . . . . . . 11
3.4. Ejemplo 6: Teorema fundamental de la aritmética . . . . . 12
3.5. Ejemplo 7: Problema de los sellos postales . . . . . . . . . 13

4. Definiciones Recursivas 13
4.1. Concepto fundamental . . . . . . . . . . . . . . . . . . . . 13
4.2. Ejemplos de definiciones recursivas . . . . . . . . . . . . . 14
4.3. Relación entre recursión e inducción . . . . . . . . . . . . . 14
4.4. Estructuras de datos recursivas (introducción) . . . . . . . 15
4.5. Algoritmos recursivos . . . . . . . . . . . . . . . . . . . . . 15

5. Ejercicios Resueltos 16
5.1. Ejercicio 1: Suma de impares (repaso) . . . . . . . . . . . . 16
5.2. Ejercicio 2: Suma de los primeros n números pares . . . . . 17
5.3. Ejercicio 3: Desigualdad con n2 . . . . . . . . . . . . . . . 17
5.4. Ejercicio 4: Divisibilidad por 9 . . . . . . . . . . . . . . . . 18
5.5. Ejercicio 5: Sucesión definida recursivamente . . . . . . . . 18

1
6. Ejercicios Propuestos 19

7. Sugerencias y Errores Comunes 21

7.1. Checklist para tus demostraciones . . . . . . . . . . . . . . 21
7.2. Errores comunes y cómo evitarlos . . . . . . . . . . . . . . 21
7.3. Preguntas frecuentes (FAQ) . . . . . . . . . . . . . . . . . 22
7.4. Frases clave para empezar cada parte . . . . . . . . . . . . 23

8. Resumen Visual 23

9. Conclusión 24

2
1. Introducción: ¿Por qué aprender inducción?
Nota importante
Como futuros ingenieros de software, la inducción matemática será
una de sus herramientas más valiosas. ¿Por qué?
Para verificar que los bucles terminan y hacen lo correcto
Para demostrar que los algoritmos recursivos funcionan
Para analizar la complejidad de programas
Para razonar sobre estructuras de datos como listas y árbo-
les

1.1. El problema fundamental

Imaginen que quieren convencer a alguien de que la fórmula

n(n + 1)
1 + 2 + 3 + ··· + n =
2
es cierta para cualquier número natural n.

No pueden probar con n = 1, luego con n = 2, luego con n = 3... ¡eso

serı́a infinito!
La inducción les da un argumento finito que cubre todos los casos.

1.2. La analogı́a del dominó

Paso inductivo: Si P (k) cae, entonces P (k + 1) cae

Caso base P (1) P (2) P (3) P (4) P (5)

Conclusión: Si el primero cae, caen todos

3
 Sugerencia
La inducción funciona como los dominós:
1. Caso base: El primer dominó cae (verificamos P (1))
2. Paso inductivo: Si un dominó cae, el siguiente también cae (si
P (k) es cierto, entonces P (k + 1) es cierto)
3. Conclusión: ¡Todos los dominós caen! (P (n) es cierto para todo
n)

2. Inducción Simple (Primer Principio)

2.1. Definición formal
Definición
Sea P (n) una proposición que depende de n ∈ N. Si:

1. Caso base: P (1) es verdadera.

2. Paso inductivo: Para todo k ≥ 1,

SI P (k) es verdadera, ENTONCES P (k + 1) es verdadera.

Entonces, P (n) es verdadera para todo n ∈ N.

4
2.2. Estructura de una demostración por inducción
Plantilla para demostraciones
Formato estándar (¡memorizar!)

1. Enunciar: ”Demostraremos por inducción sobre n que P (n) es

verdadera para todo n ∈ N.”
2. Caso base (n = 1): Verificar que P (1) es verdadera mediante
cálculo directo.
3. Hipótesis inductiva: Suponer que P (k) es verdadera para
algún k ≥ 1.
4. Paso inductivo: Demostrar que P (k + 1) es verdadera, usando
la hipótesis P (k).
5. Conclusión: ”Por el principio de inducción matemática, P (n)
es verdadera para todo n ∈ N.”

Sugerencia
Usa colores en tus demostraciones:
Azul: Hipótesis inductiva (lo que suponemos)
Rojo: Tesis (lo que queremos demostrar)
Negro: Manipulaciones algebraicas

5
2.3. Ejemplo 1: Suma de los primeros n naturales
Ejemplo
Demostrar que para todo n ∈ N:
n(n + 1)
1 + 2 + 3 + ··· + n =
2
Solución:
Paso 1: Sea P (n) : 1 + 2 + · · · + n = n(n+1)
2 .
1(1+1)
Paso 2 (Caso base n = 1): 1 = 2 = 22 = 1. ¡Verdadero!
Paso 3 (Hipótesis inductiva): Supongamos que P (k) es verdadero
para algún k ≥ 1. Es decir:
k(k + 1)
1 + 2 + ··· + k =
2
Paso 4 (Paso inductivo): Demostremos P (k + 1):

1 + 2 + · · · + k + (k + 1) = [1 + 2 + · · · + k] + (k + 1)

Aplicamos la hipótesis:
k(k + 1)
= + (k + 1)
2
Factorizamos (k + 1):
   
k k+2 (k + 1)(k + 2)
= (k + 1) + 1 = (k + 1) =
2 2 2

Que es exactamente (k+1)((k+1)+1)

2 , es decir P (k + 1).
Paso 5 (Conclusión): Por el principio de inducción matemática,
P (n) es verdadero para todo n ∈ N.

6
2.4. Ejemplo 2: Suma de los primeros n impares
Ejemplo
Demostrar que para todo n ∈ N:

1 + 3 + 5 + · · · + (2n − 1) = n2

Solución:
Paso 1: P (n) : 1 + 3 + 5 + · · · + (2n − 1) = n2 .
Paso 2 (Caso base n = 1): 1 = 12 = 1
Paso 3 (Hipótesis): Supongamos que:

1 + 3 + · · · + (2k − 1) = k 2

Paso 4 (Paso inductivo): Demostremos para k + 1:

1+3+· · ·+(2k−1)+(2(k+1)−1) = [1 + 3 + · · · + (2k − 1)]+(2k+1)

Aplicamos la hipótesis:

= k 2 + (2k + 1) = k 2 + 2k + 1 = (k + 1)2

Que es (k + 1)2 , es decir P (k + 1).

Conclusión: Por inducción, la suma de los primeros n impares es n2
para todo n ∈ N.

7
2.5. Ejemplo 3: Desigualdad (útil en análisis de algoritmos)
Ejemplo
Demostrar que 2n > n para todo n ∈ N.
Solución:
Paso 1: P (n) : 2n > n.
Paso 2 (Caso base n = 1): 21 = 2 > 1
Paso 3 (Hipótesis): Supongamos que 2k > k para algún k ≥ 1.
Paso 4 (Paso inductivo): Demostremos 2k+1 > k + 1:

2k+1 = 2 · 2k > 2 · k (por hipótesis)

Ahora, necesitamos ver que 2k ≥ k + 1 para k ≥ 1:

2k − (k + 1) = k − 1 ≥ 0 para k ≥ 1

Por tanto:
2k+1 > 2k ≥ k + 1 ⇒ 2k+1 > k + 1
Que es 2k+1 > k + 1, es decir P (k + 1).
Conclusión: Por inducción, 2n > n para todo n ∈ N.

8
2.6. Ejemplo 4: Divisibilidad
Ejemplo
Demostrar que n3 − n es divisible por 3 para todo n ∈ N.
Solución:
Paso 1: P (n) : n3 − n = 3m para algún entero m.
Paso 2 (Caso base n = 1): 13 − 1 = 0 = 3 · 0
Paso 3 (Hipótesis): Supongamos que k 3 − k = 3t para algún entero
t.
Paso 4 (Paso inductivo): Demostremos para k + 1:

(k + 1)3 − (k + 1) = (k 3 + 3k 2 + 3k + 1) − (k + 1)
= k 3 + 3k 2 + 3k + 1 − k − 1
= (k 3 − k) + 3(k 2 + k)
= 3t + 3(k 2 + k)
= 3(t + k 2 + k)

Por tanto, (k + 1)3 − (k + 1) es múltiplo de 3.

Conclusión: Por inducción, n3 −n es divisible por 3 para todo n ∈ N.

3. Inducción Fuerte (Segundo Principio)

3.1. ¿Cuándo necesitamos inducción fuerte?
Advertencia
La inducción simple no siempre es suficiente. ¿Cuándo necesitamos
inducción fuerte?
Cuando P (k + 1) depende de varios valores anteriores (no
solo de P (k))
Ejemplo clásico: Sucesión de Fibonacci (Fn = Fn−1 + Fn−2 )
Problemas donde necesitas ”mirar más atrás”que el caso inme-
diato anterior

9
3.2. Definición formal
Definición
Sea P (n) una proposición que depende de n ∈ N. Si:

1. Casos base: P (1), P (2), . . . , P (m) son verdaderas (para algún

m).
2. Paso inductivo: Para todo k ≥ m,

SI P (1), P (2), . . . , P (k) son verdaderas, ENTONCES P (k+1) es verdadera.

Entonces, P (n) es verdadera para todo n ∈ N.

Sugerencia
Regla de oro:
Si para probar P (k+1) solo necesitas P (k)  Inducción simple
Si necesitas P (k − 1), P (k − 2), . . .  Inducción fuerte

10
3.3. Ejemplo 5: Sucesión de Fibonacci
Ejemplo
La sucesión de Fibonacci se define como:

F1 = 1, F2 = 1, Fn = Fn−1 + Fn−2 para n ≥ 3

Demostrar que Fn < 2n para todo n ∈ N.

Solución:
Paso 1: P (n) : Fn < 2n .
Paso 2 (Casos base):
n = 1: F1 = 1 < 21 = 2
n = 2: F2 = 1 < 22 = 4
Paso 3 (Hipótesis inductiva fuerte): Supongamos que para todo
i ≤ k (con k ≥ 2) se cumple Fi < 2i .
Paso 4 (Paso inductivo): Demostremos Fk+1 < 2k+1 .
Por definición, Fk+1 = Fk + Fk−1 .
Aplicamos la hipótesis a i = k y i = k − 1:

Fk < 2k y Fk−1 < 2k−1

Entonces:

Fk+1 < 2k + 2k−1 = 2k−1 (2 + 1) = 3 · 2k−1 < 4 · 2k−1 = 2k+1

Por tanto, Fk+1 < 2k+1 .

Paso 5 (Conclusión): Por inducción fuerte, Fn < 2n para todo
n ∈ N.

11
3.4. Ejemplo 6: Teorema fundamental de la aritmética
Ejemplo
Demostrar que todo entero n ≥ 2 puede expresarse como producto de
números primos.
Solución:
Paso 1: P (n) : n es producto de primos.
Paso 2 (Caso base n = 2): 2 es primo, por tanto es producto de
primos (él mismo).
Paso 3 (Hipótesis inductiva fuerte): Supongamos que todo entero
m con 2 ≤ m ≤ k puede expresarse como producto de primos.
Paso 4 (Paso inductivo): Consideremos n = k + 1.

Caso 1: Si k + 1 es primo, entonces ya está expresado.

Caso 2: Si k+1 es compuesto, entonces k+1 = a·b con 2 ≤ a ≤ k
y 2 ≤ b ≤ k.
Por hipótesis inductiva, tanto a como b pueden expresarse como
producto de primos. Por tanto, k + 1 también.

Paso 5 (Conclusión): Por inducción fuerte, todo entero n ≥ 2 es

producto de primos.

12
3.5. Ejemplo 7: Problema de los sellos postales
Ejemplo
Demostrar que cualquier cantidad de franqueo de 12 centavos o más
puede formarse usando solo sellos de 4 y 5 centavos.
Solución:
Paso 1: P (n) : n puede formarse con sellos de 4 y 5.
Paso 2 (Casos base): Verificamos 12, 13, 14, 15:
12 = 4 + 4 + 4
13 = 4 + 4 + 5
14 = 4 + 5 + 5
15 = 5 + 5 + 5
Paso 3 (Hipótesis inductiva fuerte): Supongamos que podemos
formar todas las cantidades desde 12 hasta k (con k ≥ 15).
Paso 4 (Paso inductivo): Queremos formar k + 1.
Observamos que (k + 1) − 4 = k − 3 ≥ 12 (pues k ≥ 15). Por hipótesis
inductiva, k − 3 puede formarse con sellos de 4 y 5. Añadiendo un
sello de 4, obtenemos k + 1.
Paso 5 (Conclusión): Por inducción fuerte, cualquier cantidad ≥ 12
puede formarse con sellos de 4 y 5.

4. Definiciones Recursivas
4.1. Concepto fundamental
Definición
Una definición recursiva define un objeto en términos de sı́ mismo,
pero con casos base que detienen la recursión.
Estructura:
1. Caso(s) base: Se definen explı́citamente los casos más simples.
2. Caso recursivo: Se define el objeto en términos de versiones
más pequeñas de sı́ mismo.

13
4.2. Ejemplos de definiciones recursivas
Ejemplo
(
1 si n = 0 (caso base)
n! =
n · (n − 1)! si n ≥ 1 (caso recursivo)

Ejemplo
(
1 si n = 0 (caso base)
an =
a · an−1 si n ≥ 1 (caso recursivo)

Ejemplo

1
 si n = 1 (caso base)
Fn = 1 si n = 2 (caso base)

Fn−1 + Fn−2 si n ≥ 3 (caso recursivo)


4.3. Relación entre recursión e inducción

Teorema
Si una sucesión está definida recursivamente, las propiedades sobre
ella suelen demostrarse por inducción (simple o fuerte).

Ejemplo
Demostrar que el factorial es siempre positivo.
Solución:
Caso base: 0! = 1 > 0
Hipótesis: Supongamos k! > 0
Paso: (k + 1)! = (k + 1) · k! > 0 (producto de positivos)

14
4.4. Estructuras de datos recursivas (introducción)
Definición
Una lista puede definirse recursivamente como:
Caso base: La lista vacı́a ∅ es una lista.
Caso recursivo: Si L es una lista y x es un elemento, entonces
(x, L) es una lista.

Definición
Un árbol binario es:
Caso base: El árbol vacı́o (null) es un árbol binario.
Caso recursivo: Si T1 y T2 son árboles binarios, entonces el
árbol con raı́z r, hijo izquierdo T1 e hijo derecho T2 es un árbol
binario.

Sugerencia
La inducción sobre estas estructuras se llama inducción estructural
y la veremos en la próxima semana. ¡Es exactamente lo mismo que la
inducción numérica, pero aplicada a estructuras de datos!

4.5. Algoritmos recursivos

Toda definición recursiva da lugar naturalmente a un algoritmo recur-
sivo:
Ejemplo
función factorial(n):
si n = 0 entonces
retornar 1
sino
retornar n * factorial(n-1)

15
 Ejemplo
función fibonacci(n):
si n = 1 o n = 2 entonces
retornar 1
sino
retornar fibonacci(n-1) + fibonacci(n-2)

Advertencia
Cuidado: Fibonacci recursivo es muy ineficiente (O(2n )). La versión
iterativa es lineal. Esto muestra que no toda recursión es eficiente,
aunque sea elegante.

5. Ejercicios Resueltos
5.1. Ejercicio 1: Suma de impares (repaso)
Ejercicio
Demostrar por inducción que:

1 + 3 + 5 + · · · + (2n − 1) = n2

Solución completa:
Paso 1 (Enunciado): Sea P (n) : 1 + 3 + · · · + (2n − 1) = n2 .
Paso 2 (Caso base n = 1): 1 = 12
Paso 3 (Hipótesis): Supongamos P (k) verdadero:

1 + 3 + · · · + (2k − 1) = k 2

Paso 4 (Paso inductivo): Demostremos P (k + 1):

1 + 3 + · · · + (2k − 1) + (2(k + 1) − 1) = [1 + 3 + · · · + (2k − 1)] + (2k + 1)

= k 2 + (2k + 1)
= k 2 + 2k + 1
= (k + 1)2

Paso 5 (Conclusión): Por inducción, P (n) es verdadero para todo n ∈ N.

16
5.2. Ejercicio 2: Suma de los primeros n números pares
Ejercicio
Demostrar por inducción que:

2 + 4 + 6 + · · · + 2n = n(n + 1)

Solución:
Paso 1: P (n) : 2 + 4 + · · · + 2n = n(n + 1).
Paso 2 (Caso base n = 1): 2 = 1(1 + 1) = 2
Paso 3 (Hipótesis): 2 + 4 + · · · + 2k = k(k + 1).
Paso 4 (Paso inductivo):
2 + 4 + · · · + 2k + 2(k + 1) = [2 + 4 + · · · + 2k] + 2(k + 1)
= k(k + 1) + 2(k + 1)
= (k + 1)(k + 2)
= (k + 1)((k + 1) + 1)
Conclusión: Por inducción, la fórmula es válida para todo n ∈ N.

5.3. Ejercicio 3: Desigualdad con n2

Ejercicio
Demostrar que 2n ≥ n2 para todo n ≥ 4.

Solución:
Paso 1: P (n) : 2n ≥ n2 , para n ≥ 4.
Paso 2 (Caso base n = 4): 24 = 16 ≥ 42 = 16
Paso 3 (Hipótesis): Supongamos 2k ≥ k 2 para algún k ≥ 4.
Paso 4 (Paso inductivo): Queremos 2k+1 ≥ (k + 1)2 .
2k+1 = 2 · 2k ≥ 2 · k 2 (por hipótesis)
Necesitamos demostrar que 2k 2 ≥ (k + 1)2 para k ≥ 4.
Desarrollamos:
2k 2 − (k + 1)2 = 2k 2 − (k 2 + 2k + 1) = k 2 − 2k − 1
Para k ≥ 4, k 2 − 2k − 1 ≥ 16 − 8 − 1 = 7 > 0.
Por tanto, 2k 2 ≥ (k + 1)2 y entonces:
2k+1 ≥ 2k 2 ≥ (k + 1)2
Conclusión: Por inducción, 2n ≥ n2 para todo n ≥ 4.

17
5.4. Ejercicio 4: Divisibilidad por 9
Ejercicio
Demostrar que 10n − 1 es divisible por 9 para todo n ∈ N.

Solución:
Paso 1: P (n) : 10n − 1 = 9m para algún entero m.
Paso 2 (Caso base n = 1): 101 − 1 = 9 = 9 · 1
Paso 3 (Hipótesis): 10k − 1 = 9t para algún entero t.
Paso 4 (Paso inductivo):

10k+1 − 1 = 10 · 10k − 1
= 10(10k − 1) + 10 − 1
= 10(9t) + 9
= 9(10t + 1)
Conclusión: Por inducción, 10n − 1 es divisible por 9 para todo n ∈ N.

5.5. Ejercicio 5: Sucesión definida recursivamente

Ejercicio
Sea la sucesión definida por:

a1 = 2, a2 = 3, an = 2an−1 − an−2 para n ≥ 3

1. Calcula a3 , a4 , a5 .
2. Conjetura una fórmula cerrada para an .
3. Demuestra tu conjetura por inducción.

Solución:
Parte (a):
a3 = 2a2 − a1 = 2 · 3 − 2 = 6 − 2 = 4
a4 = 2a3 − a2 = 2 · 4 − 3 = 8 − 3 = 5
a5 = 2a4 − a3 = 2 · 5 − 4 = 10 − 4 = 6
Parte (b): Observamos que:

a1 = 2, a2 = 3, a3 = 4, a4 = 5, a5 = 6

18
Conjetura: an = n + 1.
Parte (c): Demostración por inducción fuerte.
Casos base:
n = 1: a1 = 2 = 1 + 1
n = 2: a2 = 3 = 2 + 1
Hipótesis inductiva fuerte: Supongamos que ai = i + 1 para todo i ≤ k
(con k ≥ 2).
Paso inductivo: Demostremos para k + 1:

ak+1 = 2ak − ak−1 = 2(k + 1) − k = 2k + 2 − k = k + 2 = (k + 1) + 1

Conclusión: Por inducción fuerte, an = n + 1 para todo n ∈ N.

6. Ejercicios Propuestos
Ejercicio
Demuestra por inducción que:
n(n + 1)(2n + 1)
12 + 22 + 32 + · · · + n2 =
6

Ejercicio
Demuestra por inducción que:
 2
n(n + 1)
13 + 23 + 33 + · · · + n3 =
2

Ejercicio
Demuestra que n2 + n es par para todo n ∈ N.

Ejercicio
Demuestra que 3n > n3 para todo n ≥ 4.

Ejercicio
Demuestra que 11n − 4n es divisible por 7 para todo n ∈ N.

19
Ejercicio
La sucesión de Lucas se define como:

L1 = 1, L2 = 3, Ln = Ln−1 + Ln−2 para n ≥ 3

Demuestra que Ln < (7/3)n para todo n ∈ N.

Ejercicio
Demuestra que cualquier cantidad de franqueo de 24 centavos o más
puede formarse usando solo sellos de 5 y 7 centavos.

Ejercicio
Define recursivamente la sucesión de los números pares positivos y
demuestra por inducción que el n-ésimo término es 2n.

Ejercicio
Sea la sucesión definida por:

a1 = 1, a2 = 2, an = 3an−1 − 2an−2 para n ≥ 3

1. Calcula a3 , a4 , a5 .
2. Conjetura una fórmula cerrada para an .
3. Demuestra tu conjetura por inducción.

Ejercicio
Demuestra que el número de diagonales de un polı́gono convexo de n
lados es n(n−3)
2 para n ≥ 3.

20
7. Sugerencias y Errores Comunes
7.1. Checklist para tus demostraciones
Plantilla para demostraciones
Antes de entregar una demostración por inducción, verifica:

¿Identifiqué claramente la proposición P (n)?

¿Verifiqué el caso base (el correcto, no siempre n = 1)?
Escribı́ explı́citamente la hipótesis inductiva?
¿Usé la hipótesis inductiva en el paso inductivo?
¿Llegué exactamente a P (k + 1) (no a otra cosa)?
¿Escribı́ la conclusión formal?

7.2. Errores comunes y cómo evitarlos

Advertencia
Error 1: Omitir el caso base
Incorrecto: ”Demostremos el paso inductivo y ya está.”
Consecuencia: La cadena de implicaciones no tiene punto de
partida.
Solución: Siempre verifica el caso base primero. ¡Es el cimiento!

Advertencia
Error 2: Usar mal la hipótesis
Incorrecto: ”Supongo P (k) y quiero P (k + 1). Es obvio porque
si sumo (k + 1)...”
Consecuencia: Estás asumiendo lo que quieres demostrar.
Solución: La hipótesis te da el valor de la suma hasta k. Úsalo
EXPLÍCITAMENTE.

21
 Advertencia
Error 3: Demostrar para un k particular
Incorrecto: ”Probemos con k = 5: funciona, entonces vale para
todos.”
Consecuencia: Solo probaste un caso, no la generalidad.
Solución: Trabaja con k como variable, no le asignes un valor
concreto.

Advertencia
Error 4: No llegar exactamente a P (k + 1)
Incorrecto: ”Llegué a (k + 1)(k + 2)/2 + 1, pero eso es casi
igual...”
Consecuencia: La demostración es incorrecta.
Solución: Antes de empezar, escribe cómo es P (k + 1). Sabrás
a dónde llegar.

7.3. Preguntas frecuentes

¿Por qué puedo suponer P (k)? ¿No es eso lo que quiero demos-
trar?
No exactamente. Quieres demostrar P (n) para todo n. La hipótesis
inductiva supone P (k) para un k arbitrario pero fijo. Es como de-
cir: ”Si me dan un caso que funciona, puedo construir el siguiente”.
No estás asumiendo la conclusión general, estás preparando el terreno
para el paso.
¿Siempre hay que empezar con n = 1?
No siempre. Si la propiedad se cumple a partir de n = 4 (como 2n ≥
n2 ), el caso base es n = 4. Pero la estructura es la misma.
¿Y si no puedo despejar algebraicamente?
A veces hay que usar trucos: sumar y restar lo mismo, factorizar, com-
pletar cuadrados. Practica manipulaciones algebraicas. Si el álgebra
es muy compleja, revisa si hay un camino más simple.
¿Cómo sé si usé bien la hipótesis?
En tu demostración, debe haber un momento donde digas explı́cita-

22
 mente ”por hipótesis inductiva sustituyas algo. Si no aparece, proba-
2

blemente no la usaste.

7.4. Frases clave para empezar cada parte

Parte Frase clave

Caso base ”Verifiquemos para n = 1: ...”
Hipótesis ”Supongamos que la propiedad es cierta para n = k, es decir: ...”
Paso inductivo ”Demostremos que entonces también es cierta para n = k + 1: ...”
Uso de hipótesis ”Por hipótesis inductiva, tenemos que ...”
Conclusión ”Por el principio de inducción matemática,
la propiedad es cierta para todo n ∈ N.”

8. Resumen Visual

INDUCCIÓN MATEMÁTICA

Inducción Simple Inducción Fuerte

Solo P (k) → P (k + 1) P (1)...P (k) → P (k + 1)

Caso Base Paso Inductivo

Verificar P (1) Si P (k) es cierto
¡El primer dominó cae! entonces P (k + 1) es cierto

Hipótesis Tesis
Supongo P (k) Demuestro P (k + 1)
Conclusión: Por inducción, vale para TODO n

23
9. Conclusión
Nota importante
La inducción matemática es una de las herramientas más poderosas
que aprenderán en este curso. Con práctica, se volverá natural. Re-
cuerden:

La inducción NO es adivinanza: Sigan la estructura paso a

paso.
La hipótesis NO es la conclusión: Es una suposición que les
ayuda a avanzar.
El álgebra SÍ importa: Practiquen manipulaciones algebrai-
cas.
La práctica HACE al maestro: Hagan muchos ejercicios.

Sugerencia
Para estudiar:
1. Lean la teorı́a con calma.
2. Reproduzcan los ejemplos resueltos sin mirar la solución.
3. Hagan los ejercicios propuestos empezando por los más simples.
4. Si se atascan, vuelvan a la plantilla y verifiquen cada paso.
5. Pregunten en clase las dudas que surjan.

Referencias Bibliográficas
Johnsonbaugh, R. (2018). Discrete Mathematics (8th ed.). Pearson.
(Capı́tulo 2)
Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th
ed.). McGraw-Hill. (Capı́tulo 5)
Grimaldi, R. P. (2003). Matemáticas Discreta y Combinatoria. Addison-
Wesley.

24
”La inducción matemática es el equivalente lógico de un bucle for
que nunca falla.
Si sabes demostrar por inducción, sabes razonar sobre cualquier
proceso iterativo.”

25