Artículos

3.5: Más sobre inducción matemática - Matemáticas


Además de las identidades, también podemos usar la inducción matemática para probar un enunciado sobre un entero positivo (n ).

Ejemplo ( PageIndex {1} label {por ejemplo: inductmultsix} )

Demuestra que (n (n + 1) (2n + 1) ) es un múltiplo de 6 para todos los enteros (n geq1 ).

Observación

Ya hemos visto cómo probar esta afirmación usando una prueba por casos, que en realidad es una forma más fácil de demostrar que (n (n + 1) (2n + 1) ) es divisible por 6. No obstante, lo demostraremos a continuación cómo utilizar la inducción para probar la afirmación.

Discusión

En la hipótesis inductiva, está claro que estamos asumiendo que (k (k + 1) (2k + 1) ) es un múltiplo de 6. En el paso inductivo, queremos demostrar que [(k + 1) (k + 2) [2 (k + 1) +1] = (k + 1) (k + 2) (2k + 3) ] también es un múltiplo de 6. Un múltiplo de 6 se puede escribir como ( 6q ) para algún número entero (q ). Como tenemos dos múltiplos de 6, necesitamos escribir [k (k + 1) (2k + 1) = 6q ] y [(k + 1) (k + 2) (2k + 3) = 6Q ] para distinguirlos. Al usar minúsculas y mayúsculas de la misma letra, indicamos que son valores diferentes. Sin embargo, debido a que provienen de la misma letra, ambos comparten algún atributo común, en este caso, los cocientes cuando los valores respectivos se dividen por 6.

Ahora, en el paso inductivo, necesitamos hacer uso de la ecuación (k (k + 1) (2k + 1) = 6q ) de la hipótesis inductiva. Esto requiere conectar el producto ((k + 1) (k + 2) (2k + 3) ) a la expresión (k (k + 1) (2k + 1) ). Como comparten el factor común (k + 1 ), lo que queda por hacer es escribir ((k + 2) (2k + 3) ) en términos de (k (2k + 1) ).

Se nos pide que probemos que (n (n + 1) (2n + 1) ) es un múltiplo de 6. Esto no es una identidad. Por lo tanto, no diga "suponga / demuestre que el identidad se sostiene cuando ... " En su lugar, diga "suponga / demuestre que el afirmar es cierto cuando ... "

Solución

Proceda por inducción en (n ). Cuando (n = 1 ), tenemos (n (n + 1) (2n + 1) = 1 cdot2 cdot3 = 6 ), que es claramente un múltiplo de 6. Por lo tanto, la afirmación es verdadera cuando (n = 1 ). Suponga que la afirmación es verdadera cuando (n = k ) para algún número entero (k geq1 ); es decir, suponga que podemos escribir [k (k + 1) (2k + 1) = 6q ] para algún número entero (q ). Queremos mostrar que la afirmación sigue siendo cierta cuando (n = k + 1 ); es decir, queremos mostrar que [(k + 1) (k + 2) [2 (k + 1) +1] = (k + 1) (k + 2) (2k + 3) = 6Q ] para algún entero (Q ). Usando la hipótesis inductiva, encontramos [ begin {alineado} (k + 1) (k + 2) (2k + 3) & = & (k + 1) (2k ^ 2 + 7k + 6) & = & (k + 1) [(2k ^ 2 + k) + (6k + 6)] & = & (k + 1) [k (2k + 1) +6 (k + 1)] & = & k (k + 1) (2k + 1) + 6 (k + 1) ^ 2 & = & 6q + 6 (k + 1) ^ 2 & = & 6 , [q + (k + 1 ) ^ 2], end {alineado} ] donde (q + (k + 1) ^ 2 ) es claramente un número entero. Esto completa la inducción.

ejercicio práctico ( PageIndex {1} label {he: induct2-01} )

Demuestre que (n ^ 2 + 3n + 2 ) es par para todos los enteros (n geq1 ).

La inducción también se puede utilizar para probar desigualdades, que a menudo requieren más trabajo para terminar.

Ejemplo ( PageIndex {2} label {por ejemplo: induct2-02} )

Demuestra que [1+ frac {1} {4} + cdots + frac {1} {n ^ 2} leq 2- frac {1} {n} ] para todos los enteros positivos (n ) .

Sequía. En la hipótesis inductiva, asumimos que la desigualdad se cumple cuando (n = k ) para algún número entero (k geq1 ). Esto significa que asumimos [ sum_ {i = 1} ^ k frac {1} {i ^ 2} leq 2- frac {1} {k}. ] En el paso inductivo, queremos mostrar que también se cumple cuando (n = k + 1 ). En otras palabras, queremos demostrar que [ sum_ {i = 1} ^ {k + 1} frac {1} {i ^ 2} leq 2- frac {1} {k + 1}. ]

Para utilizar la hipótesis inductiva, tenemos que encontrar una conexión entre estas dos desigualdades. Obviamente, tenemos [ sum_ {i = 1} ^ {k + 1} frac {1} {i ^ 2} = left ( sum_ {i = 1} ^ k frac {1} {i ^ 2} right) + frac {1} {(k + 1) ^ 2}. ] Por tanto, de la hipótesis inductiva se sigue que [ sum_ {i = 1} ^ {k + 1} frac { 1} {i ^ 2} = left ( sum_ {i = 1} ^ k frac {1} {i ^ 2} right) + frac {1} {(k + 1) ^ 2} leq 2- frac {1} {k} + frac {1} {(k + 1) ^ 2}. ] La demostración estaría completa si pudiéramos demostrar que [2- frac {1} {k} + frac {1} {(k + 1) ^ 2} leq 2- frac {1} {k + 1}. ] No hay garantía de que esta idea funcione, pero esto debería ser lo primero que intentar.

Después del reordenamiento, la desigualdad se convierte en [ frac {1} {k + 1} + frac {1} {(k + 1) ^ 2} leq frac {1} {k}, ] que es equivalente a ( frac {k + 2} {(k + 1) ^ 2} leq frac {1} {k} ). La multiplicación cruzada produce [k (k + 2) leq (k + 1) ^ 2. ] Dado que [k (k + 2) = k ^ 2 + 2k, qquad mbox {y} qquad ( k + 1) ^ 2 = k ^ 2 + 2k + 1, ] está claro que lo que queremos probar es cierto.

Pulirlo! A continuación, reorganizamos el argumento para que se lea mejor. Básicamente, todo lo que necesitamos es ejecutar el argumento. hacia atrás. Para mejorar el flujo del argumento, podemos probar un resultado separado antes de regresar al argumento principal.

Prueba 1

Proceda por inducción en (n ). Cuando (n = 1 ), el lado izquierdo se convierte en 1, al igual que el lado derecho; por tanto, la desigualdad se mantiene. Suponga que se cumple cuando (n = k ) para algún número entero (k geq1 ): [ sum_ {i = 1} ^ k frac {1} {i ^ 2} leq 2- frac { 1} {k}. ] Queremos mostrar que también se cumple cuando (n = k + 1 ): [ sum_ {i = 1} ^ {k + 1} frac {1} {i ^ 2} leq 2- frac {1} {k + 1}. ]

Para terminar la demostración, necesitamos derivar una desigualdad. Observa que [k (k + 2) = k ^ 2 + 2k

Volvamos ahora a nuestro problema original. Se deduce de la hipótesis inductiva y ([eq: induct2-ineq]) que [ begin {alineado} sum_ {i = 1} ^ {k + 1} frac {1} {i ^ 2} & = & left ( sum_ {i = 1} ^ k frac {1} {i ^ 2} right) + frac {1} {(k + 1) ^ 2} & leq & 2- frac { 1} {k} + frac {1} {(k + 1) ^ 2} & <& 2- frac {1} {k + 1}. end {alineado} ] Por lo tanto, la desigualdad aún se mantiene cuando (n = k + 1 ), lo que completa la inducción.

Observación

El paso clave en la demostración es establecer ([eq: induct2-ineq]), lo que se puede hacer mediante contradicción.

Prueba 2

Proceda por inducción en (n ). Suponga que se cumple cuando (n = k ) para algún número entero (k geq1 ): [ sum_ {i = 1} ^ k frac {1} {i ^ 2} leq 2- frac { 1} {k}. ] Queremos mostrar que también se cumple cuando (n = k + 1 ): [ sum_ {i = 1} ^ {k + 1} frac {1} {i ^ 2} leq 2- frac {1} {k + 1}. ]

Para terminar la demostración, necesitamos la siguiente desigualdad. Afirmamos que [- frac {1} {k} + frac {1} {(k + 1) ^ 2} <- frac {1} {k + 1}. label {eq: induct2-ineqalt} ] Supongamos, por el contrario, que [- frac {1} {k} + frac {1} {(k + 1) ^ 2} geq - frac { 1} {k + 1}. ] Limpia los denominadores multiplicando (k (k + 1) ^ 2 ) a ambos lados de la desigualdad. Encontramos [- (k + 1) ^ 2 + k geq -k (k + 1), ] o equivalentemente, [- k ^ 2-k-1 geq -k ^ 2-k, ] que es lo mismo que decir (- 1 geq0 ). Esta contradicción prueba que ([eq: induct2-ineqalt]) debe ser cierto.

Volvamos ahora a nuestro problema original. Se deduce de la hipótesis inductiva y ([eq: induct2-ineqalt]) que [ begin {alineado} sum_ {i = 1} ^ {k + 1} frac {1} {i ^ 2} & = & left ( sum_ {i = 1} ^ k frac {1} {i ^ 2} right) + frac {1} {(k + 1) ^ 2} & leq & 2- frac { 1} {k} + frac {1} {(k + 1) ^ 2} & <& 2- frac {1} {k + 1}. end {alineado} ] Por lo tanto, la desigualdad aún se mantiene cuando (n = k + 1 ), lo que completa la inducción.

ejercicio práctico ( PageIndex {2} label {he: induct2-02} )

Muestre que (n <2 ^ n ) para todos los enteros (n geq1 ).

No tenemos que empezar con (n = 1 ) en el paso básico. Podemos empezar con cualquier número entero (n_0 ).

Generalización. Para mostrar que (P (n) ) es verdadero para todos los enteros (n geq n_0 ), siga estos pasos:

  1. Verifique que (P (n_0) ) sea verdadero.
  2. Suponga que (P (k) ) es cierto para algún número entero (k geq n_0 ).
  3. Demuestre que (P (k + 1) ) también es cierto.

La principal diferencia está en el paso básico: necesitamos verificar que (P (n_0) ) sea verdadero. Además, en la hipótesis inductiva, debemos enfatizar que (k geq n_0 ).

Ejemplo ( PageIndex {3} label {por ejemplo: induct2-03} )

Usa la inducción matemática para demostrar que [ sum_ {i = 0} ^ n 4 ^ i = frac {1} {3} (4 ^ {n + 1} -1) ] para todos los números enteros (n geq0 ).

Solución

Proceda por inducción en (n ). Cuando (n = 0 ), el lado izquierdo se reduce a ( sum_ {i = 0} ^ 0 4 ^ i = 4 ^ 0 = 1 ), y el lado derecho se convierte en ( frac {1} {3} (4 ^ 1-1) = frac {1} {3} cdot3 = 1 ). Por tanto, la fórmula se cumple cuando (n = 0 ). Suponga que se cumple cuando (n = k ) para algún número entero (k geq0 ); es decir, suponga [ sum_ {i = 0} ^ k 4 ^ i = frac {1} {3} (4 ^ {k + 1} -1). ] Queremos demostrar que también se cumple cuando (n = k + 1 ); es decir, [ sum_ {i = 0} ^ {k + 1} 4 ^ i = frac {1} {3} (4 ^ {k + 2} -1). ] Usando la hipótesis inductiva, encuentra [ begin {alineado} sum_ {i = 0} ^ {k + 1} 4 ^ i & = & left ( sum_ {i = 0} ^ k 4 ^ i right) + 4 ^ {k +1} & = & textstyle frac {1} {3} , (4 ^ {k + 1} -1) + 4 ^ {k + 1} [3pt] & = & textstyle frac {1} {3} , (4 ^ {k + 1} -1 + 3 cdot4 ^ {k + 1}) [3pt] & = & textstyle frac {1} {3} , (4 cdot4 ^ {k + 1} -1) [3pt] & = & textstyle frac {1} {3} , (4 ^ {k + 2} -1), end {alineado} ] que es lo que queremos probar, completando así la inducción.

ejercicio práctico ( PageIndex {3} label {he: induct2-03} )

Demuestre que, para cualquier número entero (n geq0 ), [1+ frac {2} {3} + frac {4} {9} + cdots + left ( frac {2} {3} derecha) ^ n = 3 , izquierda [1- izquierda ( frac {2} {3} derecha) ^ {n + 1} derecha]. ]

Ejemplo ( PageIndex {4} label {por ejemplo: induct2-04} )

Utilice la inducción matemática para demostrar que [n ^ n geq 2 ^ n ] para todos los enteros (n geq2 ).

Solución

Proceda por inducción en (n ). Cuando (n = 2 ), la desigualdad se convierte en (2 ^ 2 geq 2 ^ 2 ), lo cual es obviamente cierto. Suponga que se cumple cuando (n = k ) para algún número entero (k geq2 ): [k ^ k geq 2 ^ k. ] Queremos demostrar que todavía se cumple cuando (n = k + 1 ): [(k + 1) ^ {k + 1} geq 2 ^ {k + 1}. ] Dado que (k geq2 ), se sigue de la hipótesis inductiva que [(k + 1) ^ {k + 1} geq k ^ {k + 1} = k cdot k ^ k geq 2 cdot 2 ^ k = 2 ^ {k + 1}. ] Por lo tanto, la desigualdad se mantiene cuando (n = k + 1 ). Esto completa la inducción.

  • Podemos usar la inducción para probar un enunciado general que involucra un entero (n ).
  • El enunciado puede ser una identidad, una desigualdad o una afirmación sobre la propiedad de una expresión que involucra (n ).
  • Una prueba de inducción no necesita comenzar con (n = 1 ).
  • Si queremos probar que un enunciado es verdadero para todos los enteros (n geq n_0 ), tenemos que verificar el enunciado para (n = n_0 ) en el paso básico.
  • Además, debemos asumir que (k geq n_0 ) en la hipótesis inductiva.

Ejercicio ( PageIndex {1} label {ex: induct2-01} )

Usa la inducción para demostrar que (n (n + 1) (n + 2) ) es un múltiplo de 3 para todos los números enteros (n geq1 ).

Ejercicio ( PageIndex {2} label {ex: induct2-02} )

Usa la inducción para demostrar que (n ^ 3 + 5n ) es un múltiplo de 6 para cualquier número entero no negativo (n ).

Ejercicio ( PageIndex {3} label {ex: induct2-03} )

Usa la inducción para demostrar que [2+ left (1+ frac {1} { sqrt {2}} + frac {1} { sqrt {3}} + cdots + frac {1} { sqrt {n}} right)> 2 sqrt {n + 1} ] para todos los enteros (n geq1 ).

Ejercicio ( PageIndex {4} label {ex: induct2-04} )

Usa la inducción para demostrar que [2 left (1+ frac {1} {8} + frac {1} {27} + cdots + frac {1} {n ^ 3} right) leq 3- frac {1} {n ^ 2} ] para todos los enteros (n geq1 ).

Ejercicio ( PageIndex {5} label {ex: induct2-05} )

Utilice la inducción para demostrar que [a + ar + ar ^ 2 + cdots + ar ^ n = frac {a (r ^ {n + 1} -1)} {r-1} ] para todos los enteros no negativos (n ), donde (a ) y (r ) son números reales con (r neq1 ).

Ejercicio ( PageIndex {6} label {ex: induct2-06} )

Usa la inducción para demostrar que, para cualquier número entero (n geq2 ), [6 sum_ {i = 2} ^ n i (i + 2) = 2n ^ 3 + 9n ^ 2 + 7n-18. ]

Ejercicio ( PageIndex {7} label {ex: induct2-07} )

Usa la inducción para demostrar que, para cualquier número entero (n geq0 ), [1- frac {2} {5} + frac {4} {25} + cdots + left (- frac {2} {5} right) ^ n = frac {5} {7} , left [1- left (- frac {2} {5} right) ^ {n + 1} right]. ]

Ejercicio ( PageIndex {8} label {ex: induct2-08} )

Usa la inducción para mostrar que (n!> 2 ^ n ) para todos los enteros (n geq4 ).

Ejercicio ( PageIndex {9} label {ex: induct2-09} )

Usa la inducción para demostrar que (n ^ 2> 4n + 1 ) para todos los enteros (n geq5 ).

Ejercicio ( PageIndex {10} label {ex: induct2-10} )

Demuestre que (2n + 1 <2 ^ n ) para todos los enteros (n geq3 ).

Ejercicio ( PageIndex {1} label {ex: induct2-01} )

Defina [S_n = frac {1} {2!} + Frac {2} {3!} + Frac {3} {4!} + Cdots + frac {n} {(n + 1)! }. ]

  1. Evalúe (S_n ) para (n = 1,2,3,4,5 ).
  2. Proponga una fórmula simple para (S_n ).
  3. Usa la inducción para probar tu conjetura para todos los números enteros (n geq1 ).

Ejercicio ( PageIndex {12} label {ex: induct2-12} )

Defina (T_n = sum_ {i = 0} ^ n frac {1} {(2i + 1) (2i + 3)} ).

  1. Evalúe (T_n ) para (n = 0,1,2,3,4 ).
  2. Proponga una fórmula simple para (T_n ).
  3. Usa la inducción para probar tu conjetura para todos los números enteros (n geq0 ).