Demostraciones e inducción · Definición

Inducción fuerte

matemáticas discretasdemostraciones

Antes de empezar necesitas conocer

Se usa cuando el caso \(k+1\) no depende solo del anterior, sino de uno o varios casos más antiguos.

Definición

La inducción fuerte prueba \(P(n)\) para todo \(n\ge n_0\): tras verificar el caso base \(P(n_0)\), se prueba \(P(k+1)\) suponiendo \(P(j)\) para todos los \(j\) con \(n_0\le j\le k\).

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

En la inducción ordinaria la hipótesis es únicamente \(P(k)\). Con frecuencia eso es poco: para factorizar \(k+1=ab\) se necesitan los factores \(a\) y \(b\), que pueden estar muy lejos de \(k\); para una recurrencia como \(F_{k+1}=F_k+F_{k-1}\) se necesitan dos términos previos. La inducción fuerte da toda la historia: se supone \(P(j)\) para cada \(j\) entre \(n_0\) y \(k\).

No es un método más potente, sino más cómodo: si se define \(Q(n)\) como «\(P(j)\) vale para todo \(j\) entre \(n_0\) y \(n\)», probar \(Q\) por inducción ordinaria equivale a la inducción fuerte sobre \(P\). Por eso ambos principios son equivalentes al buen orden de los enteros.

La parte delicada son los casos base. Si el paso usa valores hasta \(m\) lugares atrás, hay que verificar a mano los primeros \(m\) casos. Así, en el problema de las estampillas de \(4\) y \(5\) centavos, el paso de \(n-4\) a \(n\) solo vale desde \(n=16\), y los casos \(12,13,14,15\) se comprueban por separado. Olvidar uno deja la cadena rota.

Otras aplicaciones clásicas son la existencia de la factorización en primos, la fórmula cerrada de sucesiones definidas por recurrencias de dos términos y la representación binaria de cualquier entero positivo.

Para pensar

¿Por qué en la factorización en primos no basta la inducción ordinaria?

Porque si \(k+1=ab\), los factores \(a\) y \(b\) son menores que \(k+1\) pero rara vez iguales a \(k\); se necesita \(P\) para todos los valores menores.

Una fórmula para \(a_n=a_{n-1}+a_{n-2}\) se prueba verificando solo \(a_1\). ¿Qué falta?

Falta el caso \(a_2\): el paso usa dos términos anteriores y no puede aplicarse hasta \(n=3\).

Ejercicios 10

  1. En el paso de una inducción fuerte para probar \(P(k+1)\), la hipótesis es:
  2. Un paso inductivo prueba \(P(k+1)\) usando \(P(k)\) y \(P(k-1)\). ¿Cuántos casos base como mínimo hacen falta?
  3. Con \(F_1=F_2=1\) y \(F_n=F_{n-1}+F_{n-2}\), ¿cuánto vale \(F_{10}\)?
  4. Para probar que todo entero \(n\ge2\) es producto de primos, si \(k+1=ab\) con \(2\le a,b\le k\), ¿qué hipótesis se usa?
  5. Respecto a la inducción matemática ordinaria, la inducción fuerte:
  6. Sea \(a_1=1\), \(a_2=2\) y \(a_n=a_{n-1}+a_{n-2}\). ¿Cuánto vale \(a_8\)?
  7. Con estampillas de \(4\) y \(5\) centavos, ¿cuál es el menor \(n_0\) tal que toda cantidad \(n\ge n_0\) se puede formar?
  8. Sea \(a_0=0\), \(a_1=1\) y \(a_n=3a_{n-1}-2a_{n-2}\). Se prueba por inducción fuerte que \(a_n=2^n-1\). ¿Cuánto vale \(a_5\)?
  9. Se prueba que toda cantidad \(n\ge12\) se forma con estampillas de \(4\) y \(5\), pasando de \(n-4\) a \(n\). ¿Cuántos casos base hay que verificar?
  10. Para probar que todo \(n\ge1\) es suma de potencias distintas de \(2\), si \(n+1\) es par, ¿qué se usa?

Referencias

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