3.6: Inducción matemática

Última actualización
Guardar como PDF

Page ID: 118550

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Ahora pasamos a la inducción, el poderoso gemelo de la recursión.

Dejar\(n\) ser un entero positivo. Considere los siguientes enunciados matemáticos, cada uno de los cuales involucra\(n\):

\(2n+7 =13\)
\(3n-5 = 9\)
\(n^2-5n+9 = 3\)
\(8n - 3 < 48\)
\(8n - 3 > 0\)
\((n+3)(n+2)=n^2+5n+6\)
\(n^2-6n+13 \geq 0\)

Tales declaraciones se denominan declaraciones abiertas. Las sentencias abiertas pueden considerarse como ecuaciones, es decir, declaraciones que son válidas para ciertos valores de\(n\). El estado de cuenta 1 es válido sólo cuando\(n=3\). El estado 2 nunca es válido, es decir, no tiene soluciones entre los enteros positivos. El estado 3 tiene exactamente dos soluciones, y el Estado 4 tiene seis soluciones. Por otro lado, los estados 5, 6 y 7 son válidos para todos los enteros positivos.

En este punto, probablemente te estés rascando la cabeza, pensando que esta discusión es trivial. Pero consideremos algunas afirmaciones que son un poco más complejas.

La suma de los primeros enteros\(n\) positivos es\(n(n+1) / 2\).
La suma de los primeros enteros\(n\) impares positivos en\(n^2\).
\(n^n \geq n! +4,000,000,000n2^n\)cuando\(n \geq 14\).

¿Cómo podemos establecer la validez de tales afirmaciones, siempre y cuando, por supuesto, sean verdaderas? El punto de partida para dar respuesta es la siguiente propiedad:

Principio 3.11. Principio de Inducción Matemática

Let\(S_n\) Ser una declaración abierta que implica un entero positivo\(n\). Si\(S_1\) es verdadero, y si por cada entero positivo\(k\), asumiendo que la declaración\(S_k\) es verdadera implica que la declaración\(S_{k+1}\) es verdadera, entonces\(S_n\) es verdadera para cada entero positivo\(n\).

Con un poco de pensamiento, deberías ver que el Principio de Inducción Matemática es lógicamente equivalente a la Propiedad Bien Ordenada de los Enteros Positivos. Si aún no lo ha hecho, ahora podría ser un buen momento para examinar el Apéndice B sobre material de antecedentes.