Saltar al contenido

Características de la Inducción

Características de la Inducción

La inducción matemática es un método de demostración matemática utilizado para demostrar la verdad de un número infinito de proposiciones. La forma más simple y más común de inducción matemática prueba que un enunciado vale para todos los números naturales y consta de dos pasos:

  1. Caso base: mostrar que el enunciado vale para n = 0, o n = 1, dependiendo de la definición utilizada de N.
  2. Paso inductivo: mostrar que si el enunciado vale para n = k, entonces el mismo enunciado vale para n = k + 1

Este método funciona probando que el enunciado es cierto para un valor inicial, y luego probando que el proceso utilizado para ir de un valor al siguiente es válido.

Si ambas cosas son probadas, entonces cualquier valor puede obtenerse a través de la repetición de este proceso. Para entender por qué los dos pasos son suficientes, es útil pensar en el efecto dominó: si tienes una larga hilera de dominós de pie, entonces puedes asegurar que:

  1. El primer dominó caerá.
  2. Siempre que un dominó caiga, el siguiente también caerá.

Así, puedes concluir que todos los dominós caerán.

Diferencia entre inducción matemática e inducción empírica

En las ciencias naturales, se utiliza la inducción empírica. Es decir, a partir de un gran número de observaciones particulares seleccionadas adecuadamente, se formulan leyes que deben regir determinados fenómenos. La validez de un teorema matemático, sin embargo, se establece de forma completamente diferente.

En el caso de las ciencias naturales, no se puede concluir que esta afirmación es válida (como se observa en el Teorema de los cuatro colores, por ejemplo). El principio de la inducción completa se utiliza para probar que la proposición vale para todos los casos (es decir, en realidad hay una proposición para cada caso, generalmente un número infinito de casos).

Ejemplo

Supongamos que deseamos probar el siguiente enunciado para todos los números naturales n:

ecuacion 1

Esta es una fórmula simple para la suma de los números naturales de 1 a n. La prueba de que el enunciado es cierto para todos los números naturales n se da a continuación.

Verificación

El primer paso consiste en determinar el caso base de la prueba por inducción. En este caso, tomaremos como caso base n = 1. Claramente, en el lado izquierdo de la ecuación queda 5 y del lado derecho 5 * 1 (1 + 1) / 2, resolviendo da 5 = 5 => 1 = 1. Entonces el enunciado es cierto para n = 1.

Ahora necesitamos probar que el enunciado vale para n = k.

Dividiendo los dos lados del enunciado por 5 tenemos:

ecuacion 2

(Probar esta igualdad es equivalente a probar el enunciado propuesto. Podemos verificar para n = 1 que 1 = 1 * (1 + 1) / 2 => 1 = 1.)

Por hipótesis inductiva, la ecuación vale para n = k-1, es decir:

ecuacion 3

Al agregar k a ambos lados, la igualdad se mantiene, entonces:

ecuacion 4

Reescribiendo la fórmula, queda:

ecuacion 5

Luego:

ecuacion 7

Este último es el enunciado para n = k. Nótese que, asumiendo que P (K – 1) es cierto, podemos concluir que P (K) es cierto. Simbólicamente, mostramos que:

ecuacion 6

Por inducción, sin embargo, podemos concluir que el enunciado P (n) vale para todos los números naturales n.

Primero probamos el caso base (n = 1, en este caso) es verdadera.

Después, por hipótesis inductiva tenemos que P (k-1) es cierto, entonces necesitamos probar que P (k) también es cierto.

Probando que el paso inductivo es cierto, concluimos que P (n) es cierto para cualquier número n natural.