Demostración por inducción o recurrencia.
El razonamiento por inducción o recurrencia se utiliza para demostrar la validez de
proposiciones que incluyen a un número entero natural “n”.
Este método es aplicado en la demostración de proposiciones de la forma:
Para todo entero 𝒏 ≥ 𝟎 ó 𝒏 ≥ 𝟏, “algo sucede”, donde el “algo sucede” es algún enunciado
referente al entero 𝒏, por ejemplo:
1. ∀ 𝑛 ∈ ℤ, 𝑛 ≥ 1, 1 + 3 + 5 + … + (2𝑛 − 1) = 𝑛2
2. ∀ n є ℤ+ , x 𝑛 – y𝑛 , es divisible por 𝑥 – 𝑦, siendo 𝑥 e 𝑦 enteros y 𝑥 ≠ 𝑦.
3. ∀ 𝑛 ∈ ℤ, n ≥ 1, n3 + 2n , es divisible por 3.
4. ∀ n є ℤ+ , n ≥ 1, 5𝑛 – 1, es divisible por 4.
Sea 𝑷(𝒏) una proposición la cual es verdadera o falsa para cualquier entero natural 𝒏. Para
probar que 𝑷(𝒏) es verdadera para todo entero natural 𝑛 ≥ 1, es suficiente probar que:
a) 𝑷(𝟏) es verdadera.
b) Si para un entero natural 𝑛, 𝑷(𝒏) es verdadera, entonces 𝑷(𝒏 + 𝟏) es verdadera.
Entonces la proposición es verdadera para todo número natural.
Una demostración por inducción consta de dos pasos. El primero, paso fundamental, es
verificar que 𝑷(𝟏) (a veces se utiliza 𝑷(𝟎)) es verdadera. Esto se realiza con facilidad,
consiste en sustituir 𝒏 por 𝟏 y se verifica que el enunciado obtenido es verdadero mediante
algunas operaciones algebraicas o aritméticas.
En el segundo, paso inductivo, se debe llegar a la conclusión de que 𝑷(𝒏 + 𝟏) es verdadera,
utilizando la suposición de que 𝑷(𝒏) es verdadera. Esto es, si P(n) es verdadera entonces
𝑷(𝒏 + 𝟏) es verdadera.
Ejemplos: Demuestre por inducción o recurrencia.
1. ∀ 𝑛 ∈ ℤ, 𝑛 ≥ 1, 1 + 3 + 5 + … + (2𝑛 − 1) = 𝑛2
Demostración:
a) Paso Fundamental.
¿ 𝑃 (1), 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑎? (Debo probar que: [2(1) − 1] = (1)2 , es verdadera)
Observe: 2(1) − 1 = (1)2
2−1 =1
1=1
Luego 𝑃(1), es verdadera.
PROFESOR: SANTIAGO SAMUDIO AGUILAR 1
b) Paso Inductivo
Acepto que se cumple para 𝒏:
1 + 3 + 5 + … + (2𝑛 − 1) = 𝑛2 → Hipótesis de inducción.
Por demostrar que se cumple para 𝒏 + 𝟏
1 + 3 + 5 + … + (2𝑛 − 1) + [2(𝑛 + 1) − 1] = (𝑛 + 1)2
Se tiene:
1 + 3 + 5 + … + (2𝑛 − 1) = 𝑛2
Por el axioma de adición, se sigue
1 + 3 + 5 + … + (2𝑛 − 1) + [2(𝑛 + 1) − 1] = 𝑛2 + [2(𝑛 + 1) − 1]
1 + 3 + 5 + … + (2𝑛 − 1) + [2(𝑛 + 1) − 1] = 𝑛2 + (2𝑛 + 2 − 1)
1 + 3 + 5 + … + (2𝑛 − 1) + [2(𝑛 + 1) − 1] = 𝑛2 + (2𝑛 + 1)
1 + 3 + 5 + … + (2𝑛 − 1) + [2(𝑛 + 1) − 1] = 𝑛2 + 2𝑛 + 1
1 + 3 + 5 + … + (2𝑛 − 1) + [2(𝑛 + 1) − 1] = (𝑛 + 1)2
Luego, queda demostrado que: ∀ 𝑛 ∈ ℤ, 𝑛 ≥ 1, 1 + 3 + 5 + … + (2𝑛 − 1) = 𝑛2
2. ∀ n є ℤ+, x 𝑛 – y𝑛 , es divisible por 𝑥 – 𝑦, siendo 𝑥 e 𝑦 enteros y 𝑥 ≠ 𝑦.
Demostración:
3. ∀ n є ℤ+, n ≥ 1, n3 + 2n , es divisible por 3.
Demostración:
4. ∀ n є ℤ+, n ≥ 1, 5𝑛 – 1, es divisible por 4.
Demostración:
PROFESOR: SANTIAGO SAMUDIO AGUILAR 2