8.1: El principio de inducción matemática

Recordatorio\(8.1.1\).

Decir que\(P(n)\) es un predicado de números naturales, significa que, por cada número natural\(n\), tenemos una aseveración\(P(n)\) que es verdadera o falsa. Algunos ejemplos de predicados son:

• Que\(P_{odd}(n)\) sea la aserción “\(n\)es impar”.
• \(P_{big}(n)\)Sea la aseveración “\(n > 1000\).”
• \(P_{square}(n)\)Sea la aseveración “\(\exists k \in \mathbb{N},\left(n=k^{2}\right)\).”
• \(P_{prime}(n)\)Sea la afirmación “\(n\)es un número primo”.

Los matemáticos aceptan la verdad de la siguiente afirmación como un hecho básico sobre los números naturales:

Axioma\(8.1.2\). (Principle of Mathematical Induction).

Supongamos que\(P(n)\) es un predicado de números naturales. Si

1. \(P(1)\)es verdad, y
2. para cada\(k \geq 2\), (\(P(k-1) \Rightarrow P(k)\)),
   entonces\(P(n)\) es cierto para todos\(n \in \mathbb{N}^{+}\).

Aunque no podemos probar Axioma\(8.1.2\), se le puede dar una justificación informal que puede convencerte de aceptarlo como una propiedad válida de\(\mathbb{N}\):

Prueba

JUSTIFICACIÓN INFORMAL.

Dejar\(n\) ser un elemento arbitrario de\(\mathbb{N}^{+}\).

• De (i), sabemos que\(P(1)\) es verdad.
• A partir del (ii), sabemos que\(P(2-1) \Rightarrow P(2)\) es verdad.
  Ya que\(P(2-1)=P(1)\) es cierto, concluimos, por\(\Rightarrow\) -eliminación, eso\(P(2)\) es cierto.
• A partir del (ii), sabemos que\(P(3-1) \Rightarrow P(3)\) es verdad.
  Ya que\(P(3 − 1) = P(2)\) es cierto, concluimos, por\(\Rightarrow\) -eliminación, eso\(P(3)\) es cierto.
  .
  .
  .
• A partir del (ii), sabemos que\(P(n − 1) \Rightarrow P(n)\) es verdad.
  Ya que\(P(n − 1)\) es cierto, concluimos, por\(\Rightarrow\) -eliminación, eso\(P(n)\) es cierto. Ya que\(n\) es un elemento arbitrario de\(\mathbb{N}^{+}\), concluimos que\(P(n)\) es cierto para todos\(n \in \mathbb{N}^{+}\).

Terminología\(8.1.3\).

• En una prueba que usa Inducción Matemática, establecer (i) se llama el caso base, y establecer (ii) es el paso de inducción.
• En el paso de inducción, estamos demostrando\(P(k − 1) \Rightarrow P(k)\), por lo que asumimos que\(P(k − 1)\) es cierto (y establecemos\(P(k)\)). Esta suposición\(P(k−1)\) se denomina hipótesis de inducción.

Aquí hay un ejemplo de cómo se puede utilizar la inducción matemática.

Proposición\(8.1.4\).

Por cada\(n \in \mathbb{N}^{+}\), tenemos\(1+2+3+\cdots+n=\frac{n(n+1)}{2}\).

Prueba

PRUEBA POR INDUCCIÓN.

Definir\(P(n)\) para ser la aserción\[1+2+3+\cdots+n=\frac{n(n+1)}{2} .\]

1. Estuche base. Porque\(n = 1\), tenemos\[1+2+3+\cdots+n=1 \quad \text { and } \quad \frac{n(n+1)}{2}=\frac{1(1+1)}{2}=1 .\]
   Ya que estos son iguales,\(P(1)\) es cierto.
2. Paso de inducción. Supongamos que\(P(k − 1)\) es cierto (y\(k \geq 2\)). Esto significa que\[1+2+3+\cdots+(k-1)=\frac{(k-1)((k-1)+1)}{2} .\]
   Por lo tanto\ [\ begin {alineado}
   1+2 &+3+\ cdots+k\\
   & =( 1+2+3+\ cdots+ (k-1)) +k\\
   &=\ frac {(k-1) ((k-1) +1)} {2} +k\\
   &=\ frac {(k-1) k} {2} +k\\
   & amp; =k\ left (\ frac {k-1} {2} +1\ right)\\
   &=k\ left (\ frac {k+1} {2}\ right)\\
   &=\ frac {k (k+1)} {2},
   \ end {alineado}\]
   (Tercera Línea: Hipótesis de Inducción)
   así\(P(k)\) es cierto.

Por lo tanto, por el Principio de Inducción Matemática, sabemos que\(P(n)\) es cierto para todos\(n\). Esto significa\[1+2+3+\cdots+n=\frac{n(n+1)}{2}\]
para cada\(n \in \mathbb{N}^{+}\).

Remarcar\(8.1.5\).

A menudo se usa una prueba por inducción para mostrar que dos funciones\(f(n)\) y\(g(n)\) son iguales. (Proposición\(8.1.4\) es un ejemplo de esto, con\(f(n)=1+2+3+\cdots+n\) y\(g(n)=n(n+1) / 2\).) El caso base suele ser fácil: calcular\(f(1)\) y\(g(1)\), luego notar que son iguales. Por otro lado, no suele ser inmediatamente obvio cómo hacer el paso de inducción, por lo que es una buena idea comenzar haciendo algunos trabajos de scratch:

• Anote la igualdad deseada\(f(k) \stackrel{?}{=} g(k)\).
• Entonces usa simplificaciones algebraicas para llegar a una declaración verdadera. En algún momento de estas manipulaciones, utilizará la hipótesis de inducción para reemplazarla\(f(k − 1)\) con\(g(k − 1)\), o viceversa.

Entonces se puede obtener una prueba reescribiendo estos pasos algebraicos en un orden lógico (preferiblemente, como una “prueba de una línea”, una cadena de igualdades que comienza con\(f(k)\) y termina con\(g(k)\)).

Por ejemplo, el trabajo de scratch que condujo a la prueba anterior de Proposición se\(8.1.4\) puede encontrar en la Figura\(8A\) a continuación. En este caso, las manipulaciones algebraicas son bastante simples, pero algunos problemas son considerablemente más difíciles.

Figura\(8A.\) Scratch trabajo para el comprobante de Proposición\(8.1.4\).

Aquí hay otro ejemplo que es bastante sencillo:

Proposición\(8.1.6\).

Para cada\(n \in \mathbb{N}^{+}\), tenemos\[3+7+11+\cdots+(4 n-1)=2 n^{2}+n\]

Prueba

PRUEBA POR INDUCCIÓN.

Definir\(P(n)\) para ser la aserción\[3+7+11+\cdots+(4 n-1)=2 n^{2}+n .\]

1. Estuche base. Porque\(n = 1\), tenemos\[3+7+11+\cdots+(4 n-1)=3 \quad \text { and } \quad 2 n^{2}+n=2\left(1^{2}\right)+1=3 .\]
   Ya que estos son iguales,\(P(1)\) es cierto.
2. Paso de inducción. Supongamos que\(P(k − 1)\) es cierto (y\(k \geq 2\)). Esto significa que\[3+7+11+\cdots+(4(k-1)-1)=2(k-1)^{2}+(k-1) .\]
   De ahí\ [\ begin {alineado}
   3+7 &+11+\ cdots+ (4 k-1)\\
   & =( 3+7+11+\ cdots+ (4 (k-1) -1)) + (4 k-1)\\
   &=\ left (2 (k-1) ^ {2} + (k-1)\ right) + (4 k-1)\
   &= izquierda (2\ izquierda (k^ {2} - 2 k+1\ derecha) + (k-1)\ derecha) + (4 k-1)\\
   &=\ izquierda (2 k^ {2} -4 k+2\ derecha) + (k-1) + (4 k-1)\\
   &=2 k^ {2} +k,
   \ end {alineado}\]
   (Tercera Línea: Hipótesis de inducción)
   así\(P(k)\) es cierto.

Por lo tanto, por el Principio de Inducción Matemática, sabemos que\(P(n)\) es cierto para todos\(n\). Esto significa\ [3+7+11+\ cdots+ (4 n-1) =2 n^ {2} +n
por cada\(n \in \mathbb{N}^{+}\).

Ejercicio\(8.1.7\).

Probar cada fórmula por Inducción Matemática.

1. \(2+4+6+8+\cdots+2 n=n(n+1).\)
2. \(1+3+5+7+\cdots+(2 n-1)=n^{2} .\)
3. \(2+7+12+17+\cdots+(5 n-3)=\frac{n(5 n-1)}{2} .\)

Notación\(8.1.8\).

A menudo es necesario sumar una larga lista de números (como en los ejercicios anteriores), por lo que es conveniente tener una buena notación para esto: si\(a_{1}, a_{2}, \ldots, a_{n}\) hay alguna secuencia de números, entonces la suma\(a_{1}+a_{2}+\cdots+a_{n}\) puede ser denotada por\[\sum_{k=1}^{n} a_{k} .\]
(El símbolo\(\sum\) es una sigma mayúscula, la versión griega de la letra\(S\) — significa “suma”.)

Ejemplo\(8.1.9\).

Dejar\(a_{1}, a_{2}, \ldots, a_{n}\) ser una secuencia de números. Entonces:

1. \(\sum_{k=1}^{1} a_{k}=a_{1}, \quad \sum_{k=1}^{2} a_{k}=a_{1}+a_{2}, \quad \text { and } \quad \sum_{k=1}^{3} a_{k}=a_{1}+a_{2}+a_{3} .\)
2. \(\sum_{k=1}^{1} k=1, \quad \sum_{k=1}^{2} k=1+2=3, \quad \sum_{k=1}^{3} k=1+2+3=6.\)
3. \(\sum_{k=1}^{n} k=1+2+3+\cdots+n.\)
4. Para cualquier\(n \in \mathbb{N}^{+}\), tenemos\(\sum_{k=1}^{n} a_{k}=\left(\sum_{k=1}^{n-1} a_{k}\right)+a_{n}.\)

Ejercicio\(8.1.10\).

1. En Ejercicio\(8.1.7\), el lado izquierdo de cada fórmula es una suma. Escribe cada una de estas sumas en\(\sum\) notación.
2. Mostrar que (1) y (4) del Ejemplo\(8.1.9\) implican\(\sum_{k=1}^{0} a_{k}=0 .\)

Remarcar\(8.1.11\).

En el Paso de Inducción de una prueba por inducción, deseamos probar\[\forall k \geq 2,(P(k-1) \Rightarrow P(k)) .\]
Dado que\(k\) es una variable ligada (“ficticia”) en esta afirmación, no hay daño en reemplazarla por una letra diferente: por ejemplo, si lo prefieres, es perfectamente aceptable probar, digamos,\[\forall i \geq 2,(P(i-1) \Rightarrow P(i)), \quad \text { or } \quad \forall n \geq 2,(P(n-1) \Rightarrow P(n)) .\]
Esto es importante tener en cuenta cuando la variable ya\(k\) se está utilizando para otra cosa.

Ejemplo\(8.1.12\).

Demostrar que\(\sum_{k=1}^{n}(2 k-5)=n^{2}-4 n .\)

Solución

PRUEBA POR INDUCCIÓN.

Definir\(P(n)\) para ser la aserción\[\sum_{k=1}^{n}(2 k-5)=n^{2}-4 n.\]

1. Estuche base. Porque\(n = 1\), tenemos\[\sum_{k=1}^{n}(2 k-5)=\sum_{k=1}^{1}(2 k-5)=2(1)-5=-3=1^{2}-4(1)=n^{2}-4 n.\]
   Así P (1) es cierto.
2. Paso de inducción. Asumir\(n \geq 2\) y\(P(n − 1)\) es verdad. Esto significa que\[\sum_{k=1}^{n-1}(2 k-5)=(n-1)^{2}-4(n-1).\]
   Por lo tanto\ [\ begin {alineado}
   \ sum_ {k=1} ^ {n} (2 k-5) &=\ left (\ sum_ {k=1} ^ {n-1} (2 k-5)\ right) + (2 n-5)\\
   &=\ left ((n-1) ^ {2} -4 (n-1)\ right) + (2 n-5)\\
   &= izquierda (\ izquierda (n^ {2} -2 n+1\ derecha) -4 n+4\ derecha) + (2 n-5)\\
   &=n^ {2} -4 n,
   \ end {aligned}\]
   (Segunda Línea: Hipótesis de Inducción)
   así\(P(n)\) es cierto.

Por lo tanto, por el Principio de Inducción Matemática, concluimos que\(P(n)\) es cierto para todos\(n \in \mathbb{N}^{+}\).

Ejercicio\(8.1.13\).

Demostrar cada fórmula por inducción.

1. \(\sum_{k=1}^{n}(6 k+7)=3 n^{2}+10 n.\)
2. \(\sum_{k=1}^{n}(4 k-5)=2 n^{2}-3 n.\)
3. \(\sum_{k=1}^{n}(12 k-19)=6 n^{2}-13 n .\)
4. \(\sum_{k=1}^{n}(3 k+11)=\frac{3 n^{2}+25 n}{2}.\)
5. \(\sum_{k=1}^{n} 3^{k}=\frac{3^{n+1}-3}{2} .\)
6. \(\sum_{k=1}^{n} 3^{k}=\frac{3^{n+1}-3}{2}.\)
7. \(\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}.\)
8. \(\text { (harder) } \sum_{k=1}^{n} k^{3}=\left(\frac{n(n+1)}{2}\right)^{2} .\)

Remarcar\(8.1.14\).

Si deseas demostrar que eso\(P(k)\) es cierto para todos\(k\), entonces el Principio de Inducción se puede aplicar con\(k\) en el papel de\(n\). A esto se le llama “inducir”\(k\). Del mismo modo, se puede utilizar cualquier otra letra en lugar de\(n\).

Ejemplo\(8.1.15\).

Mostrar, para todos\(k \in \mathbb{N}^{+}\), que\[\sum_{i=1}^{k}\left(3 i^{2}-3 i+1\right)=k^{3} .\]

Solución

PRUEBA POR INDUCCIÓN.

Definir\(P(k)\) para ser la aserción\[\sum_{i=1}^{k}\left(3 i^{2}-3 i+1\right)=k^{3} .\]

1. Estuche base. Porque\(k = 1\), tenemos\[\sum_{i=1}^{k}\left(3 i^{2}-3 i+1\right)=\sum_{i=1}^{1}\left(3 i^{2}-3 i+1\right)=3(1)^{2}-3(1)+1=1=1^{3}=k^{3} .\]
   Así\(P(1)\) es cierto.
2. Paso de inducción. Asumir\(k \geq 2\) y\(P(k − 1)\) es verdad. Esto significa que\[\sum_{i=1}^{k-1}\left(3 i^{2}-3 i+1\right)=(k-1)^{3} .\]
   De ahí\ [\ begin {aligned}
   \ sum_ {i=1} ^ {k}\ left (3 i^ {2} -3 i+1\ right) &=\ left (\ sum_ {i=1} ^ {k-1}\ left (3 i^ {2} -3 i+1\ right)\ right) +\ left (3 k^ {2} -3 k+1\ right)\\
   & =( 1) ^ {3} +\ izquierda (3 k^ {2} -3 k+1\ derecha)\\
   &=\ left (k^ {3} -3 k^ {2} +3 k-1\ right) +\ left (3 k^ {2} -3 k+1\ right)\\
   &=k^ {3},
   \ end {alineado}\]
   (Segunda Línea: Hipótesis de Inducción)
   así\(P(k)\) es cierto.

Por el Principio de Inducción Matemática, concluimos que eso\(P(k)\) es cierto para todos\(k \in \mathbb{N}^{+}\).