7.1: Principio de Inducción Matemática

Axioma\(\PageIndex{1}\)

Supongamos que\(P(n)\) es un predicado donde la variable\(n\) tiene dominio el positivo, números enteros. Si

\(P(1)\)es verdad, y

\((\forall k) (P(k) \rightarrow P(k+1))\)es verdad,

entonces\((\forall n)P(n)\) es cierto.

Es habitual tomar como axioma el principio de inducción matemática; es decir, suponemos que la inducción matemática es válida sin probarla.

Una mirada hacia adelante.

Discutiremos un poco más sobre los axiomas en el Capítulo 8.

A continuación se muestra un esquema de la idea detrás de por qué es razonable suponer que la inducción matemática es válida. Sin embargo, este esquema no constituye una prueba ya que técnicamente utiliza implícitamente la inducción matemática.

Idea

Supongamos que\(n\) es fijo. Tenemos una secuencia de argumentos válidos:

\ (\ begin {ecuación}
\ begin {array}
P (1)\ fila derecha P (2) &\ qquad P (2)\ fila derecha P (3) &\ qquad\ cdots &\ qquad P (n-1)\ fila derecha P (n)\\
P (1) &\ qquad P (2) &\ qquad P (n-1)\
\ hline P (2) &\ hline\ qquad P (3) && \ hline\ qquad P (n)
\ end {array}
\ end {ecuación}\)

Cada uno es válido (modus ponens). Entonces, si hacemos los dos supuestos establecidos en los principios (es decir, eso\(P(1)\) es cierto y eso siempre\(P(k) \rightarrow P(k+1)\) es cierto) podemos rastrear el flujo de la verdad desde las premisas hasta la conclusión en cada argumento a su vez:

Definición: Primer argumento

Premisas verdaderas así que la conclusión es verdadera.

Definición: Segundo argumento

Premisas verdaderas (usando conclusión del primer argumento) por lo que la conclusión es verdadera.

Definición: Tercer argumento

...

Definición:\((n-1)^{th}\) argument

Premisas verdaderas (usando conclusión del\((n-2)^{th}\) argumento) por lo que la conclusión es verdadera.

La conclusión del\((n-1)^{th}\) argumento es\(P(n)\text{,}\) así\(P(n)\) es cierto.

Ahora bien, aquí hay alguna terminología específica asociada a las pruebas por inducción.

Definición: Caso base

la declaración\(P(1)\) en una prueba por inducción matemática

Definición: Paso de Inducción

la porción de una prueba por inducción matemática que establece la declaración\((\forall k) ( P(k) \rightarrow P(k+1) )\)

Definición: Hipótesis de inducción

el supuesto\(P(k)\) hecho como primer paso en el paso de inducción de una prueba por inducción matemática

Procedimiento\(\PageIndex{1}\): Proof by Induction

Para probar una declaración universal indexada por números enteros:

Estuche base.
Comience por probar la declaración obtenida del predicado universalmente cuantificado para el caso base\(n = 1\text{.}\)

Paso de inducción.
A continuación, supongamos que\(k\) es un número fijo tal que\(k \ge 1\text{,}\) y que la afirmación obtenida del predicado universalmente cuantificado es cierta para\(n = k\text{.}\) Con base en esta suposición, tratar de probar que el siguiente caso, también\(n=k+1\text{,}\) es cierto.

Ejemplo\(\PageIndex{1}\)

Demostrar que la suma de los primeros enteros\(n\) positivos es

\ begin {ecuación*}\ dfrac {n (n+1)} {2}\ texto {.} \ end {ecuación*}

Solución

Queremos probar\((\forall n)P(n)\text{,}\) dónde\(P(n)\) está de la siguiente manera.

\ begin {reunir*} P (1)\ colon\:\: 1 =\ dfrac {1\ cdot 2} {2},\ qquad P (2)\ colon\:\: 1 + 2 =\ dfrac {2\ cdot 3} {2},\ qquad P (3)\ colon\:\: 1 + 2 + 3 =\ dfrac {3\ cdot 4} {2},\\\ dotsc,\ qquad P (n)\ dos puntos\:\: 1 + 2 +\ cdots + n =\ dfrac {n (n+1)} {2},\ qquad\ dotsc\ end {reunir*}

Esto lo demostraremos por inducción.

Estuche base.
\(1 = (1\cdot2)/2\)es obviamente cierto.

Paso de inducción.
Supongamos que la declaración es verdadera\(n=k\text{;}\), es decir, asumir que

\ begin {ecuación*} 1 + 2 +\ cdots + k = k (k+1) /2\ texto {.} \ end {equation*}
Queremos mostrar que esto implica que la afirmación es verdadera para\(n = k+1\text{;}\) i.e. show

\ begin {ecuación*} 1 + 2 +\ cdots + k + (k+1) = (k+1) (k+2) /2\ texto {.} \ end {equation*}
Tenemos

\ begin {alinear*} 1 + 2 +\ cdots + k + (k+1) & = (1 + 2 +\ cdots + k) + (k+1)\\ & =\ dfrac {k (k+1)} {2} + (k+1)\\ & =\ dfrac {k^2 + 3k + 2} {2}\\ & =\ dfrac {(k^2 +) (k+2)} {2}\ texto {.} \ end {alinear*}

Ejemplo\(\PageIndex{2}\)

Demostrar que siempre\(n^3 + (n+1)^3 + (n+2)^3\) es divisible por\(9\) para cada\(n \ge 1\text{.}\)

Solución

Queremos probar\((\forall n)P(n)\text{,}\) dónde\(P(n)\) está de la siguiente manera.

\ begin {align*} P (1) &\ colon\ quad 1^3 + 2^3 + 3^3\ text {es divisible por} 9\\ P (2) &\ colon\ quad 2^3 + 3^3 + 4^3\ text {es divisible por} 9\\ P (3) &\ colon\ quad 3^3 + 4^3 + 5^3\ texto {es divisible por} 9\\ P (3) &\ colon\ quad 3^3 + 4^3 + 5^3\ texto {es divisible por} 9\\ &\ vdots\\ P (n) &\ dos puntos\ cuádruple n^3 + (n+1) ^3 + (n+2) ^3\ texto {es divisible por} 9\\ &\ vdots\ end {align*}
Lo demostraremos por inducción.

Estuche base.
Para\(n=1\text{,}\)\(n^3 + (n+1)^3 + (n+2)^3 = 36 = 9\cdot 4\text{.}\)

Paso de inducción.
Asumir\(k^3 + (k+1)^3 + (k+2)^3\) es divisible por\(9\text{.}\) Esto significa que existe algún número entero\(m\) para que

\ begin {ecuación*} k^3 + (k+1) ^3 + (k+2) ^3 = 9 m\ texto {.} \ end {equation*}
Queremos mostrar que también\((k+1)^3 + (k+2)^3 + (k+3)^3\) es divisible por\(9\text{.}\) Para hacer la conexión entre esta suma de cubos y la suma “caso anterior” de cubos arriba, podemos sumar (y simultáneamente restar) un\(k^3\) término:

\ begin {alinear*} (k+1) ^3 + (k+2) ^3 + (k+3) ^3 & = (k^3 + (k+1) ^3 + (k+2) ^3) + (k+3) ^3 - k^3\\ & = 9m + (k+3) ^3 - k^3\\ & = 9m + (k^3 + 9k^2 + 27k + 27) - k^3\\ & = 9 (m + k^2 + 3k + 3)\ texto {.} \ end {align*}
Ya que hemos factorizado nuestra suma de cubos en un producto\(9\text{,}\) que involucra esa suma de cubos es divisible por\(9\text{.}\)

 

 

Ejemplo\(\PageIndex{1}\)

Demostrar que\(3^{3n} + 1\) es divisible por\(7\) siempre que\(n\) sea impar.

Solución

No queremos utilizar\(n\) como nuestro índice de inducción, ya que salta de dos a dos. Pero\(n\) extraño significa que\(n = 2m - 1\) para algunos\(m\ge 1\text{,}\) así queremos probar\((\forall m)P(m)\text{,}\) dónde\(P(m)\) está de la siguiente manera.

\ begin {alinear*} P (1) &\ colon\ quad 3^3 + 1\ text {es divisible por} 7\\ P (2) &\ colon\ quad 3^9 + 1\ text {es divisible por} 7\\ P (3) &\ colon\ quad 3^ {15} + 1\ text {es divisible por} 7\\ &\ vdots\\ P (m) &\ dos puntos\ quad 3^ {6m-3} + 1\ texto {es divisible por} 7\\ &\ vdots\ end {alinear*}
Esto lo demostraremos por inducción.

Estuche base.
Para\(m=1\text{,}\)\(3^3+1 = 28 = 7\cdot 4\text{.}\)

Paso de inducción.
Asumir\(3^{6k-3} + 1\) es divisible por\(7\text{.}\) Esto significa que existe algún número entero\(\ell\) para que

\ begin {ecuación*} 3^ {6k-3} + 1 = 7\ ell\ texto {.} \ end {equation*}
Queremos mostrar\(3^{6(k+1)-3} + 1\) es divisible por\(7\text{.}\) Tenemos

\ begin {alinear*} 3^ {6 (k + 1) - 3} + 1 & = (3^ {6k - 3}) (3^6) + 1\\ & = (3^ {6k-3} + 1 - 1) (3^6) + 1\\ & = (3^ {6k-3} + 1) (3^6) - 3^6 + 1\\ & = (7\ ell) (3^6) - 728\\ & = 7 (3^6\ ell - 104)\ texto {.} \ end {align*}
Dado que tenemos nuestra expresión factorizada en un producto que involucra\(7\text{,}\) nuestra expresión es divisible por\(7\) lo deseado.

 

Observación\(\PageIndex{1}\)

La indexación de las declaraciones no tiene que comenzar en\(1\text{.}\)

Ejemplo\(\PageIndex{1}\)

Demostrar\(2^n \lt n!\) siempre\(n \ge 4\text{.}\)

Nota

Esta afirmación es en realidad falsa para\(n=1,2,3\text{.}\)

Solución

Estuche base.
Para\(n=4\text{,}\)\(2^4 = 16\) y\(4! = 24\text{.}\)

Paso de inducción.
Asumir\(2^k \lt k!\) para algunos\(k \ge 4\text{.}\) Queremos mostrar\(2^{k+1} \lt (k+1)!\text{.}\) Tenemos

\ begin {ecuación*} 2^ {k+1} = 2 (2^k)\ lt 2 (k!) \ lt (k+1) (k!) = (k+1)! \ texto {.} \ end {ecuación*}