8.2: Otras Pruebas por Inducción
- Page ID
- 116594
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
No todas las pruebas por inducción son sobre sumas:
Supongamos\(a, b, n \in \mathbb{Z}\), con\(a \equiv b(\bmod n)\). Espectáculo\(a^{k} \equiv b^{k}(\bmod n)\), para todos\(k \in \mathbb{N}^{+}\).
Solución
Inducimos en\(k\). Definir\(P(k)\) para ser la aserción\[a^{k} \equiv b^{k}(\bmod n) .\]
- Estuche base. Desde\(a^{1} = a\) y\(b^{1} = b\), la hipótesis nos\(a \equiv b(\bmod n)\) dice que\[a^{1} \equiv b^{1}(\bmod n) ,\]
así P (1) es cierto. - Paso de inducción. Supongamos\(P(k − 1)\) que es verdad. Esto significa que\[a^{k-1} \equiv b^{k-1}(\bmod n) .\]
Por supuesto, también tenemos\[a \equiv b(\bmod n) .\]
El ejercicio nos\(5.1.19(3)\) dice que el producto de cantidades congruentes es congruente, por lo que podemos multiplicar las congruencias anteriores, para concluir que\[\left(a^{k-1}\right)(a) \equiv\left(b^{k-1}\right)(b)(\bmod n) .\]
En otras palabras,\[a^{k} \equiv b^{k}(\bmod n) ,\]
así\(P(k)\) es cierto.
Por lo tanto, por el Principio de Inducción Matemática,\(P(k)\) es cierto para todos\(k \in \mathbb{N}^{+}\).
Demostrar cada una de las siguientes aseveraciones por inducción.
- \(5^{k} \equiv 5(\bmod 4)\), para cada\(k \in \mathbb{N}^{+}\).
- \(n^{3} \equiv n(\bmod 3)\)para cada\(n \in \mathbb{N}^{+}\).
El Principio de Inducción Matemática es una herramienta importante para probar cosas sobre secuencias de números en las que cada término se define a partir de términos anteriores. (Se dice que tales secuencias se definen “recursivamente” o “inductivamente”). Los números de Fibonacci son un ejemplo famoso de esto. En este caso, cada término es la suma de los dos términos anteriores:
Los números de Fibonacci\(F_{1}, F_{2}, F_{3}, \ldots\) se definen por:
- \(F_{1} = 1\),
- \(F_{2} = 1\), y
- \(F_{n} = F_{n−1} + F_{n−2}\)para\(n \geq 3\).
(Por ejemplo,\(F_{3}=F_{3-1}+F_{3-2}=F_{2}+F_{1}=1+1=2\).) En general, cada número de Fibonacci (después\(F_{2}\)) es la suma de los dos números anteriores de Fibonacci, así que los primeros números de Fibonacci son:\ [\ begin {array} {c||c|c|c|c|c|c|c}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 &\ cdots\\
\ hline F_ {n} & 1 & 1 & 2 & 3 & 5 & 8 & 13 &\ cdots
\ end {array}\]
Demostrar\(\sum_{k=1}^{n} F_{k}=F_{n+2}-1\) para todos\(n \in \mathbb{N}^{+}\).
Solución
Definir\(P(n)\) para ser la aserción\[\sum_{k=1}^{n} F_{k}=F_{n+2}-1 .\]
- Estuche base. Porque\(n = 1\), tenemos\[\sum_{k=1}^{n} F_{k}=\sum_{k=1}^{1} F_{k}=F_{1}=1=2-1=F_{3}-1=F_{1+2}-1=F_{n+2}-1 ,\]
así\(P(1)\) es cierto. - Paso de inducción. Supongamos que\(P(n − 1)\) es cierto (y\(n \geq 2\)). Entonces\ [\ comenzar {alineado}
\ suma_ {k=1} ^ {n} F_ {k} &=\ izquierda (\ suma_ {k=1} ^ {n-1} F_ {k}\ derecha) +F_ {n}\\
&=\ izquierda (F_ {(n-1) +2} -1\ derecha) +F_ {n}\\
&=\ izquierda (F_ {n+1} -1\ derecha) +F_ {n}\\
&=\ izquierda (F_ {n+1} +F_ {n}\ derecha) -1\\
&= F_ {n+2} -1
\ final {alineado}\]
(Segunda Línea: Hipótesis de Inducción, Última Línea: definición del número de Fibonacci).
Por lo tanto, por el Principio de Inducción Matemática,\(P(n)\) es cierto para todos\(n\). Esto significa\(\sum_{k=1}^{n} F_{k}=F_{n+2}-1\) para todos\(n \in \mathbb{N}^{+}\).
Demostrar cada aseveración por inducción.
- \(\sum_{k=1}^{n} F_{k}^{2}=F_{n} F_{n+1}\).
- \(F_{3k}\)es parejo, para todos\(k \in \mathbb{N}^{+}\).
- \(F_{4k}\)es divisible por 3, para todos\(k \in \mathbb{N}^{+}\).
La inducción también se puede aplicar a otras secuencias que se definen recursivamente:
Defina una secuencia\(\left\{a_{n}\right\}\) por:
- \(a_{1} = 1\), y
- \(a_{n} = 2a_{n−1} + 1\)para\(n \geq 2\).
Espectáculo\(a_{n} = 2^{n} − 1\) para todos\(n \in \mathbb{N}^{+}\).
Solución
Definir\(P(n)\) para ser la aserción\[a_{n}=2^{n}-1 .\]
- Estuche base. Porque\(n = 1\), tenemos\[a_{n}=a_{1}=1 \quad \text { and } \quad 2^{n}-1=2^{1}-1=2-1=1 .\]
Ya que estos son iguales, sabemos que eso\(P(1)\) es cierto. - Paso de inducción. Supongamos que\(P(k − 1)\) es cierto (y\(k \geq 2\)). Esto significa que\[a_{k-1}=2^{k-1}-1 .\]
Entonces\ [\ begin {aligned}
a_ {k} &=2 a_ {k-1} +1\\
&=2\ left (2^ {k-1} -1\ right) +1\\
&=\ left (2^ {k} -2\ right) +1\\
&=2^ {k} -1,
\ end {alineado}\]
( Primera Línea: definición de\(a_{k}\), Segunda Línea: Hipótesis de Inducción)
así\(P(k)\) es cierto.
Por lo tanto, por el Principio de Inducción Matemática,\(P(n)\) es cierto para todos\(n\). Esto significa\(a_{n} = 2^{n} − 1\) para todos\(n \in \mathbb{N}^{+}\).
El matemático italiano Fibonacci descubrió los números de Fibonacci en 1202, como la respuesta a un problema sobre el crecimiento poblacional de los conejos. A saber, asumir que:
- Empiezas con 1 par de conejos recién nacidos (un macho y una hembra).
- Cada hembra da a luz a otro par de conejos cada mes (un macho y una hembra), comenzando cuando tiene dos meses de edad. (Y los conejos nunca mueren.)
Esto quiere decir que las parejas de conejos que tienes en el mes n consisten en las parejas que ya tenías el mes pasado, más un par nuevo por cada par que tenías hace dos meses. Por lo tanto, si\(F_{n}\) es el número de pares en el mes enésimo, entonces\(F_{n}=F_{n-1}+F_{n-2}\). Puedes leer más sobre los números de Fibonacci en Wikipedia.
- Defina una secuencia\(\left\{b_{n}\right\}\) por:
- \(b_{1} = 4\), y
- \(b_{n} = 3b_{n−1} − 2 for \(n \geq 2\).
Espectáculo\(b_{n} = 3^{n} + 1\) para todos\(n \in \mathbb{N}^{+}\).
- Defina una secuencia\(\left\{c_{n}\right\}\) por:
- \(c_{1} = 25\), y
- \(c_{n} = 4c_{n−1} + 5^{n}\)para\(n \geq 2\).
Espectáculo\(c_{n} = 5^{n+1}\) para todos\(n \in \mathbb{N}^{+}\).
- Defina una secuencia\(\left\{d_{n}\right\}\) por:
- \(d_{1} = 3\), y
- \(d_{n} = 2d_{n−1} − n + 2\)para\(n \geq 2\).
Espectáculo\(d_{n} = 2^{n} + n\) para todos\(n \in \mathbb{N}^{+}\).
- Defina una secuencia\(\left\{e_{n}\right\}\) por:
- \(e_{1} = 2\), y
- \(e_{n} = 2e_{n−1} − n + 1\)para\(n \geq 2\).
Espectáculo\(e_{n} = n + 1\) para todos\(n \in \mathbb{N}^{+}\).
La inducción no es sólo para demostrar que las cosas son iguales. Por ejemplo, también se puede utilizar para probar desigualdades:
Demostrar\(2^{n} \geq n\) para todos\(n \in \mathbb{N}^{+}\).
Scratchwork. \ [\ begin {alineado}
2^ {n} &\ stackrel {?} {>} n\\
2\ cdot 2^ {n-1} &\ stackrel {?} {>n}\\
2 (n-1) &\ geq n\\
n &\ geq 2
\ final {alineado}\]
(Tercera Línea: Hipótesis de Inducción, Última Línea:\(\sqrt{ }\))
Solución
Definir\(P(n)\) para ser la aserción\[2^{n}>n\]
- Estuche base. Porque\(n = 1\), tenemos\[2^{n}=2^{1}=2>1=n,\]
así\(P(1)\) es cierto. - Paso de inducción. Supongamos que\(P(n − 1)\) es cierto (y\(n \geq 2\)). Esto significa que\[2^{n-1}>n-1 .\]
Entonces\ [\ comenzar {alineado}
2^ {n} &=2\ cdot 2^ {n-1}\\
&>2 (n-1)\\
&=n+ (n-2)\\
&\ geq n+0\\
&=n,
\ end {alineado}\]
(Segunda Línea: Hipótesis de Inducción, Cuarta Línea:\(n \geq 2\), entonces\(n - 2 \geq 0\))
así\(P(n)\) es cierto.
Por lo tanto, por el Principio de Inducción Matemática,\(P(n)\) es cierto para cada número natural\(n\).
- Demostrar\(3^{n} \geq 3n\) para todos\(n \in \mathbb{N}^{+}\). [Pista: Tenga en cuenta que\(3^{n} − 3^{n−1} > 3n − 3(n − 1)\) si\(n \geq 2\).]
- Demostrar\((1 + x)^{n} \geq 1 + nx\) para todos\(x \in \mathbb{R}^{+}\) y para todos\(n \in \mathbb{N}^{+}\).
Aquí hay un consejo estándar:
Siempre que necesites probar una declaración con una n en ella, deberías considerar usar inducción.
(asume familiaridad con polinomios). Demostrar por inducción sobre\(n\) que el polinomio\(x^{n} − y^{n}\) es divisible por\(x − y\), para todos\(n \in N\mathbb{+}\). [Pista: ¿Qué es\((x − y)x^{n} + y(x^{n} − y^{n})\)?]
(asume la familiaridad con los grupos conmutativos). Supongamos que\((G, +)\) es un grupo conmutativo. Para\(g \in G\) y\(n \in \mathbb{N}^{+}\), definimos\(ng\) recursivamente, por:\[1 g=g \quad \text { and } \quad(n+1) g=n g+g .\]
Demostrar por inducción en\(n\) eso\((m + n)g = mg + ng\) para todos\(m, n \in \mathbb{N}^{+}\).
Explique qué tiene de malo la siguiente famosa “prueba” de que todos los caballos tienen el mismo color.
INTENTO DE UNA PRUEBA POR INDUCCIÓN.
Definir\(P(n)\) para ser la aserción
“En cada grupo de n caballos, todos los caballos tienen el mismo color”.
- Estuche base. Para\(n = 1\), que\(H\) sea cualquier juego de\(n\) caballos. Ya que\(n = 1\), solo hay un caballo adentro\(H\), por lo que es obvio que todos los caballos en\(H\) tienen el mismo color.
- Paso de inducción. Supongamos, por cada juego de\(n − 1\) caballos, que todos los caballos tienen el mismo color (y\(n \geq 2\)). Que\(H\) sea cualquier juego de\(n\) caballos.
Retire un caballo\(h_{1}\) de\(H\) para formar un juego\(H_{1}\) de\(n − 1\) caballos. Por la hipótesis de inducción, sabemos que
(\(8.2.15\)) todos los caballos\(H_{1}\) tienen el mismo color.
Ahora, quita algún otro caballo\(h_{2}\) de\(H\) para formar un juego diferente\(H_{2}\) de\(n−1\) caballos. Al aplicar de nuevo la hipótesis de inducción, sabemos que
(\(8.2.16\)) todos los caballos en H2 tienen el mismo color.
Ahora, elige\(h\) ser algún otro caballo (ni\(h_{1}\) ni\(h_{2}\)). Ya que\(h \neq h_{1}\), sabemos\(h \in H_{1}\), entonces, de (\(8.2.15\)), sabemos que todos los caballos en\(H_{1}\) tienen el mismo color que\(h\). De igual manera\(h \neq h_{2}\), ya que\(h \in H_{2}\), sabemos, entonces, de (\(8.2.16\)), sabemos que todos los caballos en\(H_{2}\) también tienen el mismo color que\(h\). Esto significa que todos los caballos\(H_{1} \cup H_{2}\) tienen el mismo color (es decir, el color del caballo\(h\)). Ya que es claro que\(H = H_{1} \cup H_{2}\) (porque\(H_{1}\) contiene todos los caballos excepto\(h_{1}\), que está en\(H_{2}\)), concluimos que todos los caballos en\(H\) tienen el mismo color.
Por el Principio de Inducción Matemática, concluimos que, en cada conjunto (finito) de caballos, todos los caballos tienen el mismo color.
ADVERTENCIA. La inducción matemática es un método que es ampliamente utilizado por matemáticos e informáticos. Sin embargo, otros científicos (y también filósofos) utilizan la palabra “inducción” para referirse a un método de razonamiento bastante diferente: la inducción científica (o “razonamiento inductivo”) es el proceso de derivar una regla general a partir de ejemplos específicos. (Es lo opuesto al razonamiento deductivo3g, donde las conclusiones específicas se derivan de reglas generales.) Por ejemplo, un científico podría medir la longitud y el ancho de muchos rectángulos, y comparar con las áreas de los rectángulos. Él o ella encontraría que la zona siempre salía ser producto del largo con el ancho. El científico concluiría entonces (por razonamiento inductivo) que el área de cada rectángulo es producto de su longitud y su anchura. Sin embargo, esto no constituye una prueba matemática de la fórmula para el área de un rectángulo