3.4: Inducción matemática - Una introducción

La inducción matemática se puede utilizar para demostrar que una identidad es válida para todos los enteros\(n\geq1\). Aquí hay un ejemplo típico de tal identidad: De manera\[1+2+3+\cdots+n = \frac{n(n+1)}{2}.\] más general, podemos usar la inducción matemática para demostrar que una función proposicional\(P(n)\) es cierta para todos los enteros\(n\geq1\).

Definición: Inducción matemática

Para demostrar que una función proposicional\(P(n)\) es verdadera para todos los enteros\(n\geq1\), siga estos pasos:

• Paso Base: Verificar que\(P(1)\) sea cierto.
• Paso Inductivo: Mostrar que si\(P(k)\) es verdadero para algún entero\(k\geq1\), entonces también\(P(k+1)\) es cierto.

El paso base también se denomina paso de anclaje o paso inicial. Esta técnica de prueba es válida por el siguiente teorema.

Teorema\(\PageIndex{1}\label{thm:pmi}\): Principle of Mathematical Induction

Si\(S \subseteq \mathbb{N}\) tal que

• \(1\in S\), y
• \(k\in S \Rightarrow k+1\in S\),

entonces\(S=\mathbb{N}\).

Comentario

Aquí hay un boceto de la prueba. De (i), lo sabemos\(1\in S\). Se deduce entonces de (ii) que\(2\in S\). Aplicando nuevamente el (ii), lo encontramos\(3\in S\). De igual manera\(4\in S\), entonces\(5\in S\), y así sucesivamente. Como este argumento puede continuar indefinidamente, lo encontramos\(S = \mathbb{N}\).

Hay un problema sutil con este argumento. No está claro por qué “y así sucesivamente” va a funcionar. Después de todo, ¿qué significa realmente “y así sucesivamente” o “continuar de esta manera”? ¿Realmente puede continuar indefinidamente? El problema es que no tenemos una definición formal de los números naturales. Resulta que no podemos probar completamente el principio de inducción matemática con solo las propiedades habituales para la suma y la multiplicación. En consecuencia, tomaremos el teorema como axioma sin dar ninguna prueba formal.

Si bien no podemos proporcionar una prueba satisfactoria del principio de inducción matemática, podemos utilizarlo para justificar la validez de la inducción matemática. Dejado\(S\) ser el conjunto de enteros\(n\) para los que una función proposicional\(P(n)\) es verdadera. El paso base de la inducción matemática lo verifica\(1\in S\). El paso inductivo muestra que eso\(k\in S\) implica\(k+1\in S\). Por lo tanto, el principio de inducción matemática lo demuestra\(S=\mathbb{N}\). De ello se deduce que\(P(n)\) es cierto para todos los enteros\(n\geq1\).

El paso base y el paso inductivo, en conjunto, prueban que\[P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots\,.\] Por lo tanto,\(P(n)\) es cierto para todos los enteros\(n\geq1\). Compara dominó de inducción con caída. Cuando cae el primer dominó, derriba al siguiente dominó. El segundo dominó a su vez derriba al tercer dominó. Eventualmente, todos los dominó serán derribados. Pero no sucederá a menos que se cumplan estas condiciones:

• El primer dominó debe caer para iniciar el movimiento. Si no cae, no se producirá ninguna reacción en cadena. Este es el paso base.
• La distancia entre dominó adyacentes debe establecerse correctamente. De lo contrario, un cierto dominó puede caerse sin derribar al siguiente. Entonces la reacción en cadena se detendrá, y nunca se completará. Mantener la distancia interdominó correcta asegura que\(P(k)\Rightarrow P(k+1)\) para cada entero\(k\geq1\).

Para probar la implicación\[P(k) \Rightarrow P(k+1)\] en el paso inductivo, necesitamos llevar a cabo dos pasos: asumiendo que eso\(P(k)\) es cierto, entonces usarlo para probar también\(P(k+1)\) es cierto. Así podemos refinar una prueba de inducción en un procedimiento de 3 pasos:

• Verifica que\(P(1)\) sea verdad.
• Supongamos que eso\(P(k)\) es cierto para algún entero\(k\geq1\).
• Demostrar que también\(P(k+1)\) es cierto.

El segundo paso, el supuesto que\(P(k)\) es cierto, a veces se denomina hipótesis inductiva o hipótesis de inducción. Así es como puede verse una prueba de inducción matemática:

La idea detrás de la inducción matemática es bastante simple. No obstante, debe entregarse con precisión.

• Asegúrese de decir “Supongamos que la identidad se mantiene para algún número entero”\(k\geq1\). No digas “Supongamos que se mantiene para todos los enteros”\(k\geq1\). Si ya sabemos que el resultado es válido para todos\(k\geq1\), entonces no hay necesidad de probar nada en absoluto.
• Asegúrese de especificar el requisito\(k\geq1\). Esto asegura que la reacción en cadena de los dominó que caen comience con el primero.
• No digas “dejar\(n=k\)” o “dejar”\(n=k+1\). El punto es que no se le está asignando el valor de\(k\) y\(k+1\) a\(n\). Más bien, estás asumiendo que la declaración es verdadera cuando es\(n\) igual\(k\), y usándola para mostrar que la declaración también se mantiene cuando\(n\) es igual\(k+1\).

Ejemplo\(\PageIndex{1}\label{eg:induct1-01}\)

Usa la inducción matemática para mostrar eso\[1+2+3+\cdots+n = \frac{n(n+1)}{2}\] para todos los enteros\(n\geq1\).

Discusión

En el paso base, sería más fácil verificar los dos lados de la ecuación por separado. El paso inductivo es el paso clave en cualquier prueba de inducción, y la última parte, la parte que prueba\(P(k+1)\) es cierta, es la parte más difícil de toda la prueba. En este sentido, es útil escribir exactamente lo que proclama la hipótesis inductiva, y lo que realmente queremos probar. En este problema, la hipótesis inductiva afirma que

\[1+2+3+\cdots+k = \frac{k(k+1)}{2}.\]

Queremos demostrar que eso también\(P(k+1)\) es cierto. ¿Qué significa\(P(k+1)\) realmente? Dice

\[1+2+3+\cdots+(k+1) = \frac{(k+1)(k+2)}{2}.\]

Compara los lados izquierdos de estas dos ecuaciones. El primero es la suma de\(k\) cantidades, y el segundo es la suma de\(k+1\) cantidades, y la cantidad extra es el último número\(k+1\). La suma de los primeros\(k\) términos es precisamente lo que tenemos en el lado izquierdo de la hipótesis inductiva. Por lo tanto, por escrito

\[1+2+3+\cdots+(k+1) = 1+2+\cdots+k+(k+1),\]

podemos reagrupar el lado derecho como

\[1+2+3+\cdots+(k+1) = [1+2+\cdots+k]+(k+1),\]

para que\(1+2+\cdots+k\) pueda ser sustituido por\(\frac{k(k+1)}{2}\), según la hipótesis inductiva. Con manipulación algebraica adicional, tratamos de mostrar que la suma hace igual a\(\frac{(k+1)(k+2)}{2}\).

Se procede por inducción en\(n\). Cuando\(n=1\), el lado izquierdo de la identidad se reduce a 1, y el lado derecho se vuelve\(\frac{1\cdot2}{2}=1\); de ahí que la identidad se mantenga cuando\(n=1\). Supongamos que se mantiene cuando\(n=k\) para algún entero\(k\geq1\); es decir, asumir que

\[1+2+3+\cdots+k = \frac{k(k+1)}{2}\]

para algún número entero\(k\geq1\). Queremos demostrar que también sostiene cuándo\(n=k+1\). En otras palabras, queremos demostrar que

\[1+2+3+\cdots+(k+1) = \frac{(k+1)(k+2)}{2}.\]

Usando la hipótesis inductiva, encontramos

\[\begin{aligned} 1+2+3+\cdots+(k+1) &=& 1+2+3+\cdots+k+(k+1) \\ &=& \frac{k(k+1)}{2}+(k+1) \\ &=& (k+1)\left(\frac{k}{2}+1\right) \\ &=& (k+1)\cdot\frac{k+2}{2}. \end{aligned}\]

Por lo tanto, la identidad también sostiene cuándo\(n=k+1\). Esto completa la inducción.

Podemos usar la notación de suma (también llamada notación sigma) para abreviar una suma. Por ejemplo, la suma en el último ejemplo se puede escribir como

\[\sum_{i=1}^n i.\]

La letra\(i\) es el índice de suma. Al poner\(i=1\) debajo\(\sum\) y\(n\) arriba, declaramos que la suma comienza con\(i=1\), y va por\(i=2\)\(i=3\), y así sucesivamente, hasta\(i=n\). La cantidad que sigue\(\sum\) describe el patrón de los términos que estamos agregando en la suma. En consecuencia,

\[\sum_{i=1}^{10} i^2 = 1^2+2^2+3^2+\cdots+10^2.\]

En general, se denota la suma de\(n\) los primeros términos en\(\{a_1,a_2,a_3,\ldots\,\}\) una secuencia\(\sum_{i=1}^n a_i\). Observe que

\[\sum_{i=1}^{k+1} a_i = \left(\sum_{i=1}^k a_i\right) + a_{k+1},\]

que proporciona el vínculo entre\(P(k+1)\) y\(P(k)\) en una prueba de inducción.

Ejemplo\(\PageIndex{2}\label{eg:induct1-02}\)

Usa la inducción matemática para mostrar que, para todos los números enteros\(n\geq1\),\[\sum_{i=1}^n i^2 = 1^2+2^2+3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}.\]

Contestar

Se procede por inducción en\(n\). Cuando\(n=1\), el lado izquierdo se reduce a\(1^2=1\), y el lado derecho se vuelve\(\frac{1\cdot2\cdot3}{6}=1\); de ahí que la identidad se mantenga cuando\(n=1\). Supongamos que se mantiene cuando\(n=k\) para algún entero\(k\geq1\); es decir, asumir que\[\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}\] para algún entero\(k\geq1\). Queremos demostrar que sigue aguantando cuando\(n=k+1\). Es decir, queremos mostrar que A\[\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)[2(k+1)+1]}{6} = \frac{(k+1)(k+2)(2k+3)}{6}.\] partir de la hipótesis inductiva, encontramos\[\begin{aligned} \sum_{i=1}^{k+1} i^2 &=& \left(\sum_{i=1}^k i^2\right) + (k+1)^2 \\ &=& \frac{k(k+1)(2k+1)}{6}+(k+1)^2 \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)[k(2k+1)+6(k+1)] \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)(2k^2+7k+6) \\ [3pt] &=& \textstyle\frac{1}{6}\,(k+1)(k+2)(2k+3). \end{aligned}\] Por lo tanto, la identidad también sostiene cuándo\(n=k+1\). Esto completa la inducción.

Ejemplo\(\PageIndex{3}\label{eg:induct1-03}\)

Usa la inducción matemática para mostrar eso\[3+\sum_{i=1}^n (3+5i) = \frac{(n+1)(5n+6)}{2}\] para todos los enteros\(n\geq1\).

Contestar

Proceder por inducción encendido\(n\). Cuando\(n=1\), el lado izquierdo se reduce a\(3+(3+5)=11\), y el lado derecho se vuelve\(\frac{2\cdot11}{2} =11\); de ahí que la identidad se mantenga cuando\(n=1\). Supongamos que se mantiene cuando\(n=k\) para algún entero\(k\geq1\); es decir, asumir que\[3+\sum_{i=1}^k (3+5i) = \frac{(k+1)(5k+6)}{2}\] para algún entero\(k\geq1\). Queremos demostrar que sigue aguantando cuando\(n=k+1\). Es decir, queremos mostrar que\[3+\sum_{i=1}^{k+1} (3+5i) = \frac{[(k+1)+1]\,[5(k+1)+6]}{2} = \frac{(k+2)(5k+11)}{2}.\] A partir de la hipótesis inductiva, encontramos\[\begin{aligned} 3+\sum_{i=1}^{k+1} (3+5i) &=& \left(3+\sum_{i=1}^k (3+5i)\right) + [3+5(k+1)] \\ &=& \frac{(k+1)(5k+6)}{2} + 5k+8 \\ [3pt] &=& \textstyle\frac{1}{2}\,[(k+1)(5k+6)+2(5k+8)] \\ [3pt] &=& \textstyle\frac{1}{2}\,(5k^2+21k+22) \\ [3pt] &=& \textstyle\frac{1}{2}\,(k+2)(5k+11). \end{aligned}\] Esto completa la inducción.

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

Es hora de que escribas tu propia prueba de inducción. Demuéstralo\[1\cdot2 + 2\cdot3 + 3\cdot4 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}\] para todos los enteros\(n\geq1\).

Comentario

Te damos una mano en este, después de lo cual, estarás por tu cuenta. Disponemos la plantilla, todo lo que necesitas hacer es rellenar los espacios en blanco.

Contestar

para algún número entero\(k\geq1\). Queremos demostrar que también se sostiene cuando\(n=k+1\); es decir, queremos mostrar que

De la hipótesis inductiva se deduce que\[\begin{aligned} \hskip2in &=& \hskip2in + \hskip1in \\ [6pt] \hskip2in &=& \hskip1in + \hskip1in \\ [6pt] \hskip2in &=& \hskip1in . \end{aligned}\] Esto completa la inducción.

ejercicio\(\PageIndex{2}\label{he:induct1-02}\)

Utilice la inducción para demostrar que, para todos los enteros positivos\(n\),\[1\cdot2\cdot3 + 2\cdot3\cdot4 + \cdots + n(n+1)(n+2) = \frac{n(n+1)(n+2)(n+3)}{4}.\]

ejercicio\(\PageIndex{3}\label{he:sumfourn}\)

Utilice la inducción para demostrar que, para todos los enteros positivos\(n\),\[1+4+4^2+\cdots+4^n = \frac{1}{3}\,(4^{n+1}-1).\]

Se deben completar los tres pasos de una prueba de inducción; de lo contrario, la prueba puede no ser correcta.

Ejemplo\(\PageIndex{4}\label{eg:induct1-04}\)

Nunca intentes probarlo\(P(k)\Rightarrow P(k+1)\) solo con ejemplos. Considerar\[P(n): \qquad n^2+n+11 \mbox{ is prime}.\] En el paso inductivo, queremos probar que\[P(k) \Rightarrow P(k+1) \qquad\mbox{ for \emph{any} } k\geq1.\] La siguiente tabla verifica que es cierto para\(1\leq k\leq 8\):\[\begin{array}{|*{10}{c|}} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline n^2+n+11 & 13 & 17 & 23 & 31 & 41 & 53 & 67 & 83 & 101 \\ \hline \end{array}\] Sin embargo, cuando\(n=10\),\(n^2+n+11=121\) es compuesto. Entonces\(P(9) \nRightarrow P(10)\). El escalón inductivo se descompone cuando\(k=9\).

Ejemplo\(\PageIndex{5}\label{eg:induct1-05}\)

El paso base es igualmente importante. Considera probar\[P(n): \qquad 3n+2 = 3q \mbox{ for some integer $q$}\] para todos\(n\in\mathbb{N}\). Supongamos que\(P(k)\) es cierto para algún entero\(k\geq1\); es decir, asumir\(3k+2=3q\) para algún entero\(q\). Entonces\[3(k+1)+2 = 3k+3+2 = 3+3q = 3(1+q).\] Por lo tanto, se\(3(k+1)+2\) puede escribir en la misma forma. Esto prueba que también\(P(k+1)\) es cierto. ¿Sigue que\(P(n)\) es cierto para todos los enteros\(n\geq1\)? Sabemos que\(3n+2\) no se puede escribir como múltiplo de 3. ¿Cuál es el problema?

Solución

El problema es: necesitamos\(P(k)\) ser ciertos para al menos un valor de\(k\) para iniciar la secuencia de implicaciones\[P(1) \Rightarrow P(2), \qquad P(2) \Rightarrow P(3), \qquad P(3) \Rightarrow P(4), \qquad\ldots\] La inducción falla porque no hemos establecido el paso base. De hecho,\(P(1)\) es falso. Como el primer dominó no cae, ni siquiera podemos iniciar la reacción en cadena.

Comentario

Hasta el momento, hemos aprendido a utilizar la inducción matemática para probar identidades. En general, podemos utilizar la inducción matemática para probar una afirmación sobre\(n\). Esta afirmación puede tomar la forma de una identidad, una desigualdad, o simplemente una declaración verbal sobre\(n\). Aprenderemos más sobre la inducción matemática en las próximas secciones.

Resumen y revisión

• La inducción matemática se puede utilizar para demostrar que una declaración acerca de\(n\) es verdadera para todos los enteros\(n\geq1\).
• Tenemos que completar tres pasos.
• En el paso base, verificar la declaración para\(n=1\).
• En la hipótesis inductiva, supongamos que la sentencia sostiene cuando\(n=k\) para algún entero\(k\geq1\).
• En el paso inductivo, utilice la información recopilada de la hipótesis inductiva para probar que la declaración también sostiene cuándo\(n=k+1\).
• Asegúrese de completar los tres pasos.
• Preste atención a la redacción. Al inicio, siga de cerca la plantilla. Cuando te sientas cómodo con todo el proceso, puedes comenzar a aventurarte por tu cuenta.

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

Usa la inducción para demostrarlo\[1^3+2^3+3^3+\cdots+n^3 = \frac{n^2(n+1)^2}{4}\] para todos los enteros\(n\geq1\).

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

Utilice la inducción para probar que la siguiente identidad se mantiene para todos los enteros\(n\geq1\):\[1+3+5+\cdots+(2n-1) = n^2.\]

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

Usa la inducción para mostrar eso\[1+\frac{1}{3}+\frac{1}{3^2}+\cdots+\frac{1}{3^n} = \frac{3}{2}\left(1-\frac{1}{3^{n+1}}\right)\] para todos los enteros positivos\(n\).

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

Utilice la inducción para establecer la siguiente identidad para cualquier entero\(n\geq1\):\[1-3+9-\cdots+(-3)^n = \frac{1-(-3)^{n+1}}{4}.\]

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

Usa la inducción para mostrar que, para cualquier entero\(n\geq1\):\[\sum_{i=1}^n i\cdot i! = (n+1)!-1.\]

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

Utilice la inducción para probar la siguiente identidad para los números enteros\(n\geq1\):\[\sum_{i=1}^n \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1}.\]

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

Evaluar\(\dd\sum_{i=1}^n \frac{1}{i(i+1)}\) para algunos valores de\(n\). ¿Cuál crees que debería ser el resultado? Usa la inducción para probar tu conjetura.

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

Usa la inducción para demostrar que\[\sum_{i=1}^n (2i-1)^3 = n^2(2n^2-1)\] siempre\(n\) es un entero positivo.

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

Usa la inducción para mostrar que, para cualquier entero\(n\geq1\):\[1^2-2^2+3^2-\cdots+(-1)^{n-1}n^2 = (-1)^{n-1}\,\frac{n(n+1)}{2}.\]

Ejercicio\(\PageIndex{10}\label{ex:induct1-10}\)

Usa la inducción matemática para mostrar eso\[\sum_{i=1}^n \frac{i+4}{i(i+1)(i+2)} = \frac{n(3n+7)}{2(n+1)(n+2)}\] para todos los enteros\(n\geq1\).