Demostraciones e inducción · Definición

Inducción matemática

matemáticas discretasdemostraciones

Antes de empezar necesitas conocer

Permite probar de una sola vez una propiedad para infinitos enteros, reduciendo el problema a un caso inicial y a un paso que se repite.

Definición

La inducción matemática prueba que una propiedad \(P(n)\) vale para todo entero \(n\ge n_0\): se verifica el caso base \(P(n_0)\) y se prueba que, para cada \(k\ge n_0\), \(P(k)\) implica \(P(k+1)\).

\[\big[P(n_0)\wedge\forall k\ge n_0\,(P(k)\Rightarrow P(k+1))\big]\Rightarrow\forall n\ge n_0\,P(n)\]

La idea es la de una fila de fichas de dominó: el caso base tumba la primera ficha y el paso inductivo garantiza que, si cae la ficha \(k\), cae la siguiente. Entonces caen todas desde la primera. Formalmente descansa en el principio del buen orden de los enteros no negativos: si \(P(n)\) fallara para algún \(n\ge n_0\), habría un menor \(n\) donde falla, y eso contradice el paso inductivo aplicado al anterior.

En la práctica el paso inductivo se escribe así: se supone \(P(k)\) (la hipótesis inductiva) y se transforma el enunciado de \(P(k+1)\) hasta poder usarla. En sumas, se separa el último término; en divisibilidad, se escribe la expresión de \(k+1\) como un múltiplo de la de \(k\) más algo divisible. Por ejemplo, para \(1+2+\cdots+n=\tfrac{n(n+1)}2\), sumar \(k+1\) a ambos lados de \(P(k)\) da \(\tfrac{(k+1)(k+2)}2\).

Los errores típicos son tres: omitir el caso base (como en «\(n=n+1\)», cuyo paso es válido pero cuya conclusión es falsa), empezar la cadena en un \(n_0\) donde la propiedad ya no vale, y usar en el paso la propiedad para \(k+1\), que es justo lo que se quiere probar. Conviene escribir siempre, antes de empezar, qué dice \(P(k)\) y qué dice \(P(k+1)\).

Este método prepara la inducción fuerte, donde la hipótesis incluye todos los casos anteriores, y la definición recursiva de sucesiones y estructuras, cuyas propiedades casi siempre se prueban por inducción.

Para pensar

¿Por qué no basta verificar \(P(n)\) para \(n=1,\dots,1000\)?

Mil casos no prueban nada sobre \(n=1001\); la inducción sí, porque el paso inductivo cubre todo \(k\) a la vez. Hay propiedades que valen hasta números enormes y luego fallan.

En una prueba por inducción, ¿qué se supone y qué se prueba en el paso?

Se supone \(P(k)\) y se prueba \(P(k+1)\); suponer \(P(k+1)\) sería razonar en círculo.

Ejercicios 10

  1. Una demostración por inducción matemática consta de:
  2. Para probar \(2+4+\cdots+2n=n(n+1)\), en el caso base \(n=1\) ambos lados valen:
  3. En el paso inductivo para \(P(n)\), la hipótesis inductiva es:
  4. Usando \(1+3+\cdots+(2n-1)=n^2\), ¿cuánto suman los primeros \(12\) impares?
  5. En el paso inductivo de \(1+2+\cdots+n=\tfrac{n(n+1)}{2}\), al sumar \(k+1\) a ambos lados de \(P(k)\) el lado derecho es igual a:
  6. Usando \(1^2+2^2+\cdots+n^2=\tfrac{n(n+1)(2n+1)}{6}\), calcula \(1^2+2^2+\cdots+6^2\).
  7. Para probar que \(6\) divide a \(7^n-1\), ¿qué igualdad permite pasar de \(P(k)\) a \(P(k+1)\)?
  8. La desigualdad \(2^n>n^2\) falla para \(n=2,3,4\) y vale para \(n\ge5\). ¿Qué caso base es adecuado para probarla por inducción?
  9. Sea \(P(n)\): «\(n=n+1\)». Se prueba que \(P(k)\Rightarrow P(k+1)\) sumando \(1\) a ambos lados. ¿Qué se concluye?
  10. Se verifica \(P(3)\) y se prueba \(P(k)\Rightarrow P(k+1)\) para todo \(k\ge3\). ¿Para qué valores de \(n\) queda probado \(P(n)\)?

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §5.1
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §5.2
  • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond, 1st edition, Springer, 2003. Cap. 1