Demostración por inducción matemática

Una de las técnicas más útiles para demostrar una cadena de hechos \(S(n)\) para \(n \in \mathbb{Z}^{+}\) es la demostración por inducción matemática.

Hay dos pasos principales para demostrar una cadena de hechos por inducción matemática:

1. Demostración del caso base
Demostramos que se cumple el hecho para un número entero inicial, comúnmente es el número \(1\), pero puede ser otro valor. Éste es el paso más fácil.

En este paso hay que demostrar directamente que el hecho se cumple para \(n=a\) dónde \(a\) es el entero inicial. Como parte de la inducción matemática se demostrará que la propiedad se cumple para este valor (demostración directa) y para todos los enteros arriba de este valor (demostración indirecta).

Para demostrar el caso base basta con mostrar que \(S(a)\) se cumple. Como ya se mencionó, lo más común es que se tenga que demostrar \(S(1)\). Sin embargo, puede que se le pida que empiece con otros valores como por ejemplo: \(S(0)\), \(S(2)\), \(S(-1)\), \(S(4)\), etc.

2. El paso inductivo
El paso inductivo es el paso más complicado. En este paso se tiene que demostrar que: "Si el hecho se cumple para algún valor \(n = k\) entonces el hecho se cumplirá para el siguiente valor \(n = k+1\)".

Consiste en demostrar que:
\[\textrm{Si } S(k) \textrm{ se cumple, entonces } S(k+1) \textrm{ se cumple}\]
\[S(k) \textrm{ se cumple} \Rightarrow S(k+1) \textrm{ se cumple}\]

Es decir:

1. Tomamos como hipótesis que el hecho es verdadero para algún número \(k\), sin justificación. Esta parte comúnmente se llama hipótesis de inducción.
2. Demostramos que si se cumple para algún número \(k\), entonces podemos asegurar que se cumplirá para  el número que sigue después de ese "algún" número \(k\), el número que sigue después de \(k\) es el número \(k+1\).

3. Conclusión

Juntando los dos hechos demostrados del caso baso y el paso inductivo llegamos a la conclusión que el hecho se deber de cumplir para todos los números enteros \(n \ge a\).

Por ejemplo, si demostramos 1. "\(S(1) \textrm{ se cumple}\)" y 2. "\(S(k) \textrm{ se cumple} \Rightarrow S(k+1) \textrm{ se cumple}\)" entonces usando los dos hechos podemos deducir que: "\(S(1) \textrm{ se cumple} \Rightarrow S(2) \textrm{ se cumple}\)". Luego usando este nuevo hecho con el paso inductivo tenemos que: \(S(2) \textrm{ se cumple} \Rightarrow S(3) \textrm{ se cumple}\), continuando: \(S(3) \textrm{ se cumple} \Rightarrow S(4) \textrm{ se cumple}\), \(S(4) \textrm{ se cumple} \Rightarrow S(5) \textrm{ se cumple}\), \(S(5) \textrm{ se cumple} \Rightarrow S(6) \textrm{ se cumple}\), \(S(6) \textrm{ se cumple} \Rightarrow S(7) \textrm{ se cumple}\),etc.

Para demostrarle al evaluador que entiendes la lógica de la inducción es útil practicar escribir el siguiente párrafo dónde el valor de \(a\) correspondería con el término inicial. "Entonces el hecho se cumple para \(n = k+1\) si se cumple para algún entero \(n = k\), como se cumple para \(n = a\) entonces se cumple para todo entero mayor o igual a \(a\) por inducción matemática." 

Ejemplos:

Problema 1. Demuestre usando inducción matemática que \(A(n)=6+3n\) es un múltiplo de 3 para todo valor \(n \in \mathbb{Z}^{+}\).

1.1 Demostración del caso base
\[A(1)=6+3(1)=9\] El resultado es un múltiplo de 3 ya que \((3)(3) = 9\)

1.2 El paso inductivo
Supongamos que se cumple para algún valor \(n = k\), entonces:
\[A(k)=6+3k=3a \;\;\; a \in \mathbb{Z}\]Observando el caso \(n=k+1\):
\[A(k+1)=6+3(k+1)=6+3k+3=(6+3k)+3=A(k)+3\]Aplicando la hipótesis de inducción vemos que:
\[A(k+1)=3a+3=3(a+1)\]Como \((a+1) \in \mathbb{Z}\) entonces se cumple el hecho para \(A(k+1)\) si se cumple para \(A(k)\).

1.3 Conclusión
"Entonces el hecho se cumple para \(n = k+1\) si se cumple para algún entero \(n = k\), como se cumple para \(n = 1\) entonces se cumple para todo entero mayor o igual a \(1\) por inducción matemática."

Problema 2.  Demuestre usando inducción matemática que \(a_{n}=3(4^{n})\) es divisible entre 4 para todo valor \(n \in \mathbb{Z}^{+}\).

2.1 Demostración del caso base
\[a_{1}=3(4^{1})=3(4)=12\] El resultado es un múltiplo de 4 ya que \((4)(3) = 12\)

2.2 El paso inductivo
Supongamos que se cumple para algún valor \(n = k\), entonces:
\[a_{k}=3(4^{k})=4b \;\;\; b \in \mathbb{Z}\]Observando el caso \(n=k+1\):
\[a_{k+1}=3(4^{k+1})=3(4^{k})(4)=(a_{k})(4)\]Aplicando la hipótesis de inducción vemos que:
\[a_{k+1}=(4b)(4)=4(4b)\]Como \((4b) \in \mathbb{Z}\) entonces se cumple el hecho para \(a_{k+1}\) si se cumple para \(a_{k}\).

2.3 Conclusión
"Entonces el hecho se cumple para \(n = k+1\) si se cumple para algún entero \(n = k\), como se cumple para \(n = 1\) entonces se cumple para todo entero mayor o igual a \(1\) por inducción matemática."

Problema 3. Demuestre usando inducción matemática que la suma de los primeros \(n\) enteros enteros para \(n \in \mathbb{Z}^{+}\) es igual a:\[\frac{n(n+1)}{2}\]
3.1 Demostración del caso base
Vemos que la suma del primer entero positivo es igual a 1.
Vemos que: \[\frac{1(1+1)}{2}=1\]Por lo anterior hemos demostrado que el caso base se cumple.

3.2 El paso inductivo
Supongamos que se cumple para algún valor \(n = k\), entonces:
\[\textrm{Suma de primeros } k \textrm{ enteros positivos } = \sum_{i=1}^{k}i= \frac{k(k+1)}{2}\]Observando el caso \(n=k+1\):
\[\textrm{Suma de primeros } k+1 \textrm{ enteros positivos } = \sum_{i=1}^{k+1}i\]
\[\textrm{Suma de primeros } k+1 \textrm{ enteros positivos } = \left (\sum_{i=1}^{k}i\right ) + (k+1) \]
Aplicando la hipótesis de inducción vemos que:
\[\textrm{Suma de primeros } k+1 \textrm{ enteros positivos }= \frac{k(k+1)}{2} + (k+1)\]
\[\textrm{Suma de primeros } k+1 \textrm{ enteros positivos }= \frac{k^2+k}{2} + \frac{2k+2}{2}\]
\[\textrm{Suma de primeros } k+1 \textrm{ enteros positivos }= \frac{k^2+3k+2}{2}\]
\[\textrm{Suma de primeros } k+1 \textrm{ enteros positivos }= \frac{(k+1)(k+2)}{2}\]Como tiene la forma del hecho que queremos probar entonces sí se cumple el hecho para el caso donde \(n = k+1\) si se cumple para el caso \(n = k\).

3.3 Conclusión
"Entonces el hecho se cumple para \(n = k+1\) si se cumple para algún entero \(n = k\), como se cumple para \(n = 1\) entonces se cumple para todo entero mayor o igual a \(1\) por inducción matemática."

Problema 4. Demuestre usando inducción matemática que la suma de los primeros \(n\) términos (\(n \in \mathbb{Z}^{+}\)) de una secuencia geométrica con \(r = 0.5\) y término inicial \(u_{1}=4\) es igual a:
\[8(1-(0.5)^n)\]
4.1 Demostración del caso base
Vemos que la suma del primer término es igual a 4.
Vemos que: \[8(1-(0.5)^1)=8(0.5)=4\]Por lo anterior hemos demostrado que el caso base se cumple.

4.2 El paso inductivo
Supongamos que se cumple para algún valor \(n = k\), entonces:
\[\textrm{Suma de primeros } k \textrm{ términos } = \sum_{i=1}^{k}4(0.5)^{i-1} =  8(1-(0.5)^k)\]Observando el caso \(n=k+1\):
\[\textrm{Suma de primeros } k+1 \textrm{ términos } = \sum_{i=1}^{k+1}4(0.5)^{i-1}\]
\[\textrm{Suma de primeros } k+1 \textrm{ términos } = \left (\sum_{i=1}^{k}4(0.5)^{i-1}\right ) + 4(0.5)^k\]Aplicando la hipótesis de inducción vemos que:
\[\textrm{Suma de primeros } k+1 \textrm{ términos }= 8(1-(0.5)^{k}) + 4(0.5)^{k}\]
\[\textrm{Suma de primeros } k+1 \textrm{ términos }= 8-8(0.5)^k + 4(0.5)^k\]
\[\textrm{Suma de primeros } k+1 \textrm{ términos }= 8-4(0.5)^k\]
\[\textrm{Suma de primeros } k+1 \textrm{ términos }= 8-\frac{8}{2}(0.5)^k\]
\[\textrm{Suma de primeros } k+1 \textrm{ términos }= 8-8(0.5)^{k+1}\]
\[\textrm{Suma de primeros } k+1 \textrm{ términos }= 8(1-(0.5)^{k+1})\]Como tiene la forma del hecho que queremos probar entonces sí se cumple el hecho para el caso donde \(n = k+1\) si se cumple para el caso \(n = k\).

4.3 Conclusión
"Entonces el hecho se cumple para \(n = k+1\) si se cumple para algún entero \(n = k\), como se cumple para \(n = 1\) entonces se cumple para todo entero mayor o igual a \(1\) por inducción matemática."