3.7: Inducción matemática

Introducción, primer ejemplo

En esta sección, examinaremos la inducción matemática, una técnica para probar proposiciones sobre los enteros positivos. La inducción matemática reduce la prueba de que todos los enteros positivos pertenecen a un conjunto de verdad a un número finito de pasos.

Ejemplo\(\PageIndex{1}\): Formula for Triangular Numbers

Considera la siguiente proposición sobre los enteros positivos, que etiquetaremos\(p(n)\text{:}\) La suma de los enteros positivos de 1 a\(n\) es\(\frac{n (n+1)}{2}\text{.}\) Esta es una fórmula bien conocida que es bastante sencilla de verificar para un valor dado de\(n\text{.}\) Por ejemplo,\(p(5)\) es: La suma de lo positivo enteros de 1 a 5 es\(\frac{5 (5+1)}{2}\text{.}\) Efectivamente,\(1 + 2 + 3 + 4 + 5= 15 =\frac{5(5+1)}{2}\text{.}\) Sin embargo, esto no sirve como prueba que\(p(n)\) sea una tautología. Todo lo que hemos establecido es que\(5\) está en el conjunto de verdad de\(p\text{.}\) Dado que los enteros positivos son infinitos, ciertamente no podemos usar este enfoque para probar la fórmula.

Una analogía: Una prueba por inducción matemática es similar a derribar una fila de dominó estrechamente espaciados que están de pie en el extremo. Para derribar los dominó en Figura\(\PageIndex{1}\), todo lo que necesitas hacer es empujar el primer dominó. Para estar seguros de que todos serán derribados, se debe hacer algún trabajo con anticipación. Los dominó deben posicionarse de manera que si se empuja algún dominó es derribado, empujará al siguiente dominó en la línea.

Figura\(\PageIndex{1}\): Una analogía para la inducción matemática, foto Creative Commons de Ranveig Thattai

Volviendo al Ejemplo\(\PageIndex{1}\) imagina las proposiciones\(p(1), p(2), p(3),\ldots\) de ser una línea infinita de dominó. A ver si estas proposiciones están en la misma formación que los dominó. Primero, nos centraremos en un punto específico de la línea:\(p(99)\) y no\(p(100)\text{.}\) vamos a probar que ninguna de estas proposiciones es cierta, solo que la verdad de\(p(99)\) implica la verdad de\(p(100)\text{.}\) En términos de nuestra analogía, si\(p(99)\) es derribada, se volcará\(p(100)\text{.}\)

En la prueba\(p(99) \Rightarrow p(100)\text{,}\) vamos a utilizar\(p(99)\) como nuestra premisa. Debemos probar: La suma de los enteros positivos de 1 a 100 es\(\frac{100 (100+1)}{2}\text{.}\) Empezamos por observar que la suma de los enteros positivos de 1 a 100 es Es\((1 + 2 + \cdots + 99) +100\text{.}\) decir, la suma de los enteros positivos de 1 a 100 es igual a la suma de los primeros noventa y nueve más el número final, 100. Ahora podemos aplicar nuestra premisa,\(p(99)\text{,}\) a la suma\(1 + 2 + \cdots + 99\text{.}\) Después de reordenar nuestros números, obtenemos la expresión deseada para\(1 + 2 + \cdots + 100\text{:}\)

\ begin {equation*}\ begin {split} 1 + 2 +\ cdots + 99 + 100 & = (1 + 2 +\ cdots + 99) + 100\\ & =\ frac {99\ cdot (99+1)} {2} + 100\ textrm {por nuestra suposición de} p (99)\\ & =\ frac {99\ cdot 100} {2} +\ frac {2\ cdot 100} {2}\\ & =\ frac {100\ cdot 101} {2}\\ & =\ frac {100\ cdot (100+1)} {2}\ end {split}\ texto {.} \ end {ecuación*}

Lo que acabamos de hacer es análogo a revisar dos dominónigos en una línea y encontrar que están correctamente posicionados. Ya que estamos tratando con una línea infinita, debemos verificar todos los pares a la vez. Esto se logra demostrando que\(p(n) \Rightarrow p(n + 1)\) para todos\(n \geq 1\text{:}\)

\ begin {equation*}\ begin {split} 1 + 2 +\ cdots + n + (n+1) & = (1 + 2 +\ cdots + n) + (n + 1)\\ & =\ frac {n (n+1)} {2} + (n + 1)\ textrm {por} p (n)\ & =\ frac {n (n+1)} 2} +\ frac {2 (n+1)} {2}\\ & =\ frac {(n+1) (n+2)} {2}\\ & =\ frac {(n+1) ((n+1) +1)} {2}\ end {split}\ text {.} \ end {ecuación*}

¡Todos están alineados! Ahora mira\(p(1)\text{:}\) La suma de los enteros positivos del 1 al 1 es\(\frac{1\cdot(1+1)}{2}\text{.}\) Claramente,\(p(1)\) es verdad. Esto desencadena una reacción en cadena. Ya que\(p(1) \Rightarrow p(2)\text{,}\)\(p(2)\) es cierto. Ya que\(p(2) \Rightarrow p(3)\text{,}\)\(p(3)\) es cierto; y así sucesivamente. \(\blacksquare\)

Teorema\(\PageIndex{1}\): The Principle of Mathematical Induction

Dejar\(p(n)\) ser una proposición sobre los enteros positivos. Si

1. \(p(1)\)es verdad, y
2. para todos\(n\geq 1\text{,}\)\(p(n) \Rightarrow p(n + 1)\text{,}\)

entonces\(p(n)\) es una tautología.

Nota\(\PageIndex{1}\)

La verdad de\(p(1)\) se llama la base para la prueba de inducción. La premisa que\(p(n)\) es verdadera en la segunda parte se llama hipótesis de inducción. La prueba que\(p(n)\) implica\(p(n + 1)\) se llama el paso de inducción de la prueba. A pesar de nuestra analogía, la base generalmente se hace primero en una prueba de inducción. Sin embargo, el orden realmente no importa.

Ejemplos

Ejemplo\(\PageIndex{2}\): Generalized Detachment

Consideremos la implicación sobre los enteros positivos.

\ begin {ecuación*} p (n): q_0\ fila derecha q_1, q_1\ a q_2,\ ldots, q_ {n-1}\ a q_n, q_0\ Rightarrow q_n\ end {ecuación*}

Sigue una prueba que\(p(n)\) es una tautología. Base:\(p(1)\) es\(q_0 \rightarrow q_1, q_0\Rightarrow q_1\text{.}\) Esta es la ley lógica del desapego que sabemos que es verdadera. Si aún no lo has hecho, escribe la tabla de la verdad de\(((q_0 \rightarrow q_1 )\land q_0)\to q_1\) para verificar este paso.

Inducción: Supongamos que eso\(p(n)\) es cierto para algunos\(n \geq 1\text{.}\) Queremos demostrar que\(p(n + 1)\) debe ser cierto. Es decir:

\ begin {ecuación*} q_0\ fila derecha q_1, q_1\ a q_2,\ ldots, q_ {n-1}\ a q_n, q_n\ a q_ {n+1}, q_0\ Rightarrow q_ {n+1}\ end {ecuación*}

Aquí hay una prueba directa de\(p(n + 1)\text{:}\)

Mesa\(\PageIndex{1}\)

Paso	Proposición	Justificación
\(1-(n+1)\)	\(q_0 \rightarrow q_1, q_1\to q_2, \ldots , q_{n-1}\to q_n, q_0\)	Locales
\(n+2\)	\(q_n\)	\((1)-(n+1)\),\(p(n)\)
\(n+3\)	\(q_n\to q_{n+1}\)	Premisa
\(n+4\)	\(q_{n+1}\)	\((n+2)\),\((n+3)\), desprendimiento\(\square\)

Ejemplo\(\PageIndex{3}\): An Example from Number Theory

Para todos\(n \geq 1\text{,}\)\(n^3+2n\) es un múltiplo de 3. Una prueba inductiva sigue:

Base:\(1^3+2(1)= 3\) es un múltiplo de 3. ¡La base casi siempre es así de fácil!

Inducción: Supongamos que\(n \geq 1\) y\(n^3+2n\) es un múltiplo de 3. Considera\((n+1)^3+2(n+1)\text{.}\) ¿Es un múltiplo de 3?

\ begin {ecuación*}\ begin {split} (n+1) ^3+2 (n+1) & = n^3+3 n^2+3 n^2+3 n+1+ (2n+2)\\ & = n^3+2 n + 3 n^2+3 n+3\\ & = (n^3+2 n) + 3 (n^2+ n+1)\ end {split}\ text {.} \ end {ecuación*}

Sí,\((n+1)^3+2(n+1)\) es la suma de dos múltiplos de 3; por lo tanto, también es un múltiplo de 3. \(\square\)

Ahora discutiremos algunas de las variaciones del principio de inducción matemática. El primero simplemente permite universos que son similares a\(\mathbb{P}\) tales como\(\{-2, -1, 0, 1,\ldots \}\) o\(\{5, 6, 7, 8,\ldots \}\text{.}\)

Teorema\(\PageIndex{2}\): Principle of Mathematical Induction (Generalized)

Si\(p(n)\) es una proposición sobre\(\{k_0 , k_0+ 1, k_0+ 2,\ldots \}\text{,}\) donde\(k_0\) es cualquier entero, entonces\(p(n)\) es una tautología si

1. \(p(k_0)\)es verdad, y
2. para todos\(n \geq k_0\text{,}\)\(p(n) \Rightarrow p(n + 1)\text{.}\)

Ejemplo\(\PageIndex{4}\): A Proof of the Permutations Formula

En el Capítulo 2, afirmamos que el número de diferentes permutaciones de\(k\) elementos tomados de un conjunto de\(n\) elementos, se\(P(n; k)\text{,}\) puede computar con la fórmula\(\frac{n!}{(n-k)!}\text{.}\) Podemos probar esta afirmación por inducción en\(n\text{.}\) For\(n \geq 0\text{,}\) let\(q(n)\) be the proposition

\ comenzar {ecuación*} P (n; k) =\ frac {n!} {(n-k)!} \ textrm {para todos} k\ textrm {,} 0\ le k\ le n\ texto {.} \ end {ecuación*}

Base:\(q(0)\) establece que\(P(0; 0) \) si es el número de formas en que\(0\) los elementos pueden ser seleccionados del conjunto vacío y dispuestos en orden, entonces\(P(0; 0) = \frac{0!}{0!} = 1 \text{.}\) Esto es cierto. Una ley general en combinatoria es que hay exactamente una manera de no hacer nada.

Inducción: Supongamos que\(q(n)\) es cierto para algún número natural\(n\text{.}\) Se nos deja probar que esta suposición implica que eso\(q(n +1)\) es cierto. Supongamos que tenemos un conjunto de cardinalidad\(n + 1\) y queremos seleccionar y disponer\(k\) de sus elementos. Hay dos casos a considerar, el primero de los cuales es fácil. Si\(k = 0\text{,}\) entonces hay una manera de seleccionar cero elementos del conjunto; por lo tanto

\ begin {ecuación*} P (n + 1; 0) = 1 =\ frac {(n+1)!} {(n+1+0)!} \ end {ecuación*}

y la fórmula funciona en este caso.

El caso más desafiante es verificar la fórmula cuando\(k\) es positivo y menor o igual a\(n+1\text{.}\) Aquí contamos el valor de\(P(n+ 1; k)\) contando el número de formas en que se puede llenar el primer elemento en el arreglo y luego contar el número de formas en que el resto\(k -1\) los elementos se pueden rellenar usando la hipótesis de inducción.

Hay opciones\(n + 1\) posibles para el primer elemento. Ya que eso deja\(n\) elementos para llenar las\(k - 1\) posiciones restantes, hay\(P(n; k - 1)\) formas de completar el arreglo. Por regla de los productos,

\ comenzar {ecuación*}\ comenzar {dividir} P (n +1; k) &= (n+1) P (n; k-1)\\ & = (n+1)\ frac {n!} {(n- (k-1))!} \\ & =\ frac {(n+1) n!} {(n-k+1)!} \\ & =\ frac {(n+1)!} {((n+1) -k)!} \ end {split}\ end {ecuación*}

\(\blacksquare\)

Curso de Inducción de Valores

Una segunda variación permite la expansión de la hipótesis de inducción. El principio de curso de valores incluye la generalización previa. También a veces se le llama inducción fuerte.

Teorema\(\PageIndex{3}\): The Course-of-Values Principle of Mathematical Induction

Si\(p(n)\) es una proposición sobre\(\{k_0 , k_0+ 1, k_0+ 2,\ldots \}\text{,}\) donde\(k_0\) es cualquier entero, entonces\(p(n)\) es una tautología si

1. \(p(k_0)\)es verdad, y
2. para todos\(n\geq k_0\text{,}\)\(p(k_0), p(k_0 + 1), . . . , p(n) \Rightarrow p(n + 1) \text{.}\)

Un número primo se define como un entero positivo que tiene exactamente dos divisores positivos, 1 y él mismo. Hay un número infinito de primos. La lista de primos comienza con\(2, 3, 5, 7, 11,\ldots \text{.}\)

La proposición sobre lo\(\{2, 3, 4, . . .\}\) que vamos a probar aquí es\(p(n)\text{:}\)\(n\) puede escribirse como producto de uno o más primos. En la mayoría de los textos, la afirmación de que\(p(n)\) es una tautología aparecería como

Teorema\(\PageIndex{4}\): Existence of Prime Factorizations

Cada entero positivo mayor o igual a 2 tiene una descomposición prima.

Prueba

Si encontraras este teorema fuera del contexto de una discusión de inducción matemática, podría no ser obvio que la prueba se puede hacer por inducción. Reconocer cuándo una prueba de inducción es apropiada es principalmente una cuestión de experiencia. ¡Ahora a la prueba!

Base: Dado que 2 es un primo, ya se descompone en primos (uno de ellos).

Inducción: Supongamos que para algunos\(n \geq 2\) todos los enteros\(2,3, . . . , n\) tienen una descomposición prima. Observe la hipótesis del curso de valor. Considera\(n + 1\text{.}\) O\(n + 1\) es primo o no lo es. Si\(n + 1\) es primo, ya está descompuesto en primos. Si no, entonces\(n + 1\) tiene un divisor,\(d\text{,}\) distinto de 1 y\(n + 1\text{.}\) Por lo tanto,\(n + 1 = c d\) donde ambos\(c\) y\(d\) están entre 2 y\(n\text{.}\) Por la hipótesis de inducción,\(c\) y\(d\) tienen descomposiciones primos,\(c_1 c_2 \cdots c_s\) y\(d_1 d_2 \cdots d_t\), respectivamente. Por lo tanto,\(n + 1\) tiene la descomposición principal\(c_1 c_2 \cdots c_s d_1 d_2 \cdots d_t\text{.}\)

Nota\(\PageIndex{2}\): Peano Postulates and Induction

La inducción matemática se originó a finales del siglo XIX. Dos matemáticos que destacaron en su desarrollo fueron Richard Dedekind y Giuseppe Peano. Dedekind desarrolló un conjunto de axiomas que describen los enteros positivos. Peano refinó estos axiomas y les dio una interpretación lógica. A los axiomas se les suele llamar los Postulados de Peano.

Axioma\(\PageIndex{1}\): Peano Postulates

El sistema de enteros positivos consiste en un conjunto no vacío,\(\mathbb{P}\text{;}\) un elemento mínimo de\(\mathbb{P}\text{,}\) denotado 1; y una “función sucesora”, s, con las propiedades

1. Si\(k \in \mathbb{P}\), entonces hay un elemento de\(\mathbb{P}\) llamado el sucesor de\(k\text{,}\) denotado\(s(k)\text{.}\)
2. No hay dos elementos de\(\mathbb{P}\) tener el mismo sucesor.
3. Ningún elemento de\(\mathbb{P}\) tiene\(1\) como sucesor.
4. Si\(S \subseteq \mathbb{P}\text{,}\)\(1 \in S\text{,}\) y\(k \in S \Rightarrow s(k) \in S\text{,}\) entonces\(S = \mathbb{P}\text{.}\)

Nota\(\PageIndex{3}\)

• Podrías reconocer\(s(k)\) como simplemente ser\(k + 1\text{.}\)
• Axioma 4 es el que hace posible la inducción matemática. En una prueba de inducción, simplemente aplicamos ese axioma al conjunto de verdad de una proposición.

Ejercicios

Ejercicio\(\PageIndex{1}\)

Demostrar que la suma de los primeros enteros\(n\) impares es igual\(n^2\).

Contestar

Deseamos probar que eso\(P(n):1+3+5+\cdots +(2n-1)=n^2\) es cierto para\(n \geqslant 1\text{.}\) Recordemos que el\(n\) número entero positivo impar es\(2n - 1\text{.}\)

Base: porque\(n=1\text{,}\)\(P(n)\) es\(1=1^2\text{,}\) lo que es cierto

Inducción: Supongamos que para algunos\(n\geqslant 1\text{,}\)\(P(n)\) es cierto. Entonces inferimos que\(P(n+1)\) sigue:

\ begin {ecuación*}\ begin {split} 1+3+\ cdots + (2 (n+1) -1) &= (1+3+\ cdots + (2n-1)) + (2 (n+1) -1)\\ & =n^2+ (2n+1)\ quad\ textrm {por} P (n)\ textrm {y álgebra básica}\\ ^& = (n+1) 2\ quad\ blacksquare\ end {split}\ end {ecuación*}

Ejercicio\(\PageIndex{2}\)

Demostrar que si\(n \geq 1\text{,}\) entonces\(1(1!) + 2(2!) + \cdots + n(n!) = (n + 1)! - 1\text{.}\)

Ejercicio\(\PageIndex{3}\)

Demostrar que para\(n \geq 1\text{:}\)\(\sum_{k=1}^n k^2= \frac{1}{6} n(n+1) (2 n+1)\text{.}\)

Contestar

Prueba:

• Fundamento: Observamos que la proposición es verdadera cuando\(n=1\text{:}\)\(\sum_{k=1}^{1} k^2 =1= \frac{1(2)(3)}{6}\text{.}\)
• Inducción: Supongamos que la proposición es cierta para algunos\(n \geq 1\text{.}\) Esta es la hipótesis de inducción.
  \ begin {ecuación*}\ begin {split}\ sum_ {k=1} ^ {n+1} k^2 &=\ sum_ {k=1} ^n k^2+ (n+1) ^2\\ &=\ frac {n (n+1) (2n+1)} {6} + (n+1) ^2\ qquad\ textrm {por la hipótesis de inducción}\\ &= frac {(n+1) (2n^2+7n+6)} {6}\\ &=\ frac {(n+1) (n+2) (2n+3)} {6}\ qquad\ blacksquare\\ end {split}\ end {ecuación*}
  Por lo tanto, la verdad de la proposición de\(n\) implica la verdad de la proposición de\(n+1\text{.}\)

Ejercicio\(\PageIndex{4}\)

Demostrar que para\(n \geq 0\text{:}\)\(\sum_{k=0}^n 2^k = 2^{n+1}-1\text{.}\)

Ejercicio\(\PageIndex{5}\)

Usa la inducción matemática para demostrar que para\(n\geq 1\text{,}\)

\ begin {ecuación*}\ frac {1} {1\ cdot 2} +\ frac {1} {2\ cdot 3} +\ cdots +\ frac {1} {n (n+1)} =\ frac {n} {n+1}\ texto {.} \ end {ecuación*}

Contestar

Base: Porque\(n=1\text{,}\) observamos que\(\frac{1}{(1\cdot 2)}=\frac{1}{(1+1)}\)

Inducción: Supongamos que para algunos\(n\geqslant 1\text{,}\) la fórmula es cierta.

Entonces:

\ begin {equation*}\ begin {split}\ frac {1} {(1\ cdot 2)} +\ cdots +\ frac {1} {n (n+1)} +\ frac {1} {(n+1) (n+2)} &=\ frac {n} {n+1} +\ frac {1} {(n+1) (n+2)}\\ =\ frac {(n+2) n} {(n+1) (n+2)} +\ frac {1} {(n+1) (n+2)}\\ &=\ frac {(n+1) ^2} {(n+1) (n+2)}\\ &=\ frac {n+1} {n+2}\ quad\ blacksquare\\ end {split}\ end {equ. *}

Ejercicio\(\PageIndex{6}\)

Demostrar que si\(n \geq 2\text{,}\) la Ley generalizada de DeMorgan es cierta:

\ begin {ecuación*}\ neg (p_1\ tierra p_2\ tierra\ texto {...} \ tierra p_n)\ Leftrightarrow (\ neg p_1)\ lor (\ neg p_2)\ lor\ lor\ cdots\ lor (\ neg p_n)\ text {.} \ end {ecuación*}

Contestar

Bases: (\(n=2\)) Probado con una tabla de verdad ya.

Inducción: Asumir que la Ley de DeMorgan generalizada con\(n\) proposiciones es cierta para algunos\(n\geq 2\text{.}\)

\ begin {equation*}\ begin {split}\ neg\ left (p_1\ land p_2\ land\ cdots\ land p_n\ land p_ {n+1}\ right) &\ Leftrightarrow\ neg\ left (\ left (\ left (p_1\ land p_2\ land\ cdots\ land p_n\ right)\ land p_ {n+1}\ right)\\ &\ Leftrightarrow\ neg\ left (p_1\ land p_2\ land\ cdots\ land p_n\ right)\ lor\ left (\ neg p_ {n+1}\ right)\\ & \ Leftrightarrow\ left (\ left (\ neg p_1\ right)\ lor\ left (\ neg p_2\ right)\ lor\ cdots\ lor\ left (\ neg p_n\ right)\ right)\ lor\ left (\ neg p_ {n+1}\ right)\\ &\ Leftrightarrow\ left (\ neg p_1\ right)\ lor\ izquierda (\ neg p_2\ derecha)\ lor\ cdots\ lor\ izquierda (\ neg p_n\ derecha)\ lor\ izquierda (\ neg p_ {n+1}\ derecha)\ end {split}\ end {ecuación* }

Ejercicio\(\PageIndex{7}\)

El número de cadenas de\(n\) ceros y unos que contienen un número par de unos es\(2^{n-1}\text{.}\) Probar este hecho por inducción para\(n \geq 1\text{.}\)

Contestar

Dejar\(A_n\) ser el conjunto de cadenas de ceros y unos de longitud\(n\) (suponemos que\(\lvert A_n \rvert =2^n\) se conoce). Dejar\(E_n\) ser el conjunto de las cuerdas “pares”, y\(E_{n}^{c}=\) las cuerdas impares. El problema es probar eso para\(n\geqslant 1\text{,}\)\(\lvert E_n \rvert =2^{n-1}\text{.}\) Claramente,\(\lvert E_1\rvert =1\text{,}\) y, si para algunos\(n\geqslant 1, \lvert E_n\rvert =2^{n-1}\text{,}\) se deduce que\(\lvert E_{n+1}\rvert =2^n\) por el siguiente razonamiento.

Particionamos\(E_{n+1}\) según el primer bit:\(E_{n+1}=\{1s\mid s \in E_n^c \}\cup \{ 0s \mid s \in E_n\}\)

Ya que\(\{1s\mid s \in E_n^c\}\) y\(\{0s \mid s \in E_n\}\) son disjuntas, podemos aplicar la ley de adición. Por lo tanto,

\ begin {ecuation*}\ begin {split}\ quad\ lvert E_ {n+1}\ rvert & =\ lvert e_n^C\ rvert +\ lvert e_n\ rvert\ rvert\\ & =2^ {n-1} + (2^n-2^ {n-1}) =2^n.\ quad\ blacksquare\ end {split}\ end {ecuación*}

Ejercicio\(\PageIndex{8}\)

Let\(p(n)\) be\(8^n-3^n\) es un múltiplo de 5. Demostrar que\(p(n)\) es una tautología sobre\(\mathbb{N}\text{.}\)

Ejercicio\(\PageIndex{9}\)

Supongamos que hay\(n\) gente en una habitación,\(n \geq 1\text{,}\) y que todos se dan la mano entre sí. Demostrar que se habrán producido\(\frac{n(n-1)}{2}\) apretones de manos.

Contestar

Supongamos que para\(n\) las personas se\((n\geqslant 1),\frac{(n-1)n}{2}\) realizan apretones de manos. Si una persona más entra a la habitación, le dará la mano a la\(n\) gente,

\ begin {ecuación*}\ begin {split}\ frac {(n-1) n} {2} +n & =\ frac {n^2-n+2n} {2}\\ &=\ frac {n^2+n} {2} =\ frac {n (n+1)} {2}\\ &=\ frac {((n+1) -1) (n+1)} {2}\ end {split}\ end {ecuación*}

Además, porque no\(n=1\text{,}\) hay apretones de manos, que coincida con la fórmula conjeturada:

\ begin {ecuación*}\ frac {(1-1) (1)} {2} =0\ quad\ blacksquare. \ end {ecuación*}

Ejercicio\(\PageIndex{10}\)

Demostrar que es posible hacer cualquier franqueo de ocho centavos o más utilizando únicamente sellos de tres y cinco centavos.

Ejercicio\(\PageIndex{11}\)

Asociatividad generalizada. Es bien sabido que si\(a_1\text{,}\)\(a_2\text{,}\) y\(a_3\) son números, entonces no importa en qué orden\(a_1+ a_2+a_3\) se tomen las sumas en la expresión, el resultado siempre es el mismo. Llama a este hecho\(p(3)\) y asume que es cierto. Demostrar usando la inducción de curso de valores que si\(a_1\text{,}\)\(a_2\text{,}\)\(\ldots ,\) y\(a_n\) son números, entonces no importa en qué orden\(a_1+ a_2+\cdots +a_n\) se tomen las sumas en la expresión, el resultado es siempre el mismo.

Contestar

Let\(p(n)\) be “\(a_{1} + a_2 + \cdots + a_n\)tiene el mismo valor sin importar cómo se evalúe”.

Base:\(a_1 + a_2 + a_3\) podrá evaluarse sólo de dos maneras. Ya que + es asociativo,\((a_1 + a_2) + a_3 = a_1 + (a_2 + a_3)\text{.}\) Por lo tanto,\(p(3)\) es cierto.

Inducción: Supongamos que para algunos\(n\geq 3\text{,}\)\(p(3), p(4), \dots , p(n)\) son todos ciertos. Ahora considere la suma\(a_1 + a_2 + \cdots + a_n + a_{n+1}\text{.}\) Cualquiera de las\(n\) adiciones en esta expresión se puede aplicar en último lugar. Si la suma\(j\) th se aplica último, tenemos\(c_j=(a_1+a_2+\cdots +a_j)+(a_{j+1}+\cdots +a_{n+1})\text{.}\) No importa cómo se evalúe la expresión a la izquierda y derecha de la\(j^{\text{th}}\) adición, el resultado siempre será el mismo por la hipótesis de inducción, específicamente\(p(j)\) y ahora\(p(n+1-j)\text{.}\) podemos probar que\(c_1=c_2=\cdots =c_n\text{.}\) Si \(i < j\text{,}\)

\ begin {ecuación*}\ begin {split} c_i &= (a_1+a_2+\ cdots +a_i) + (a_ {i+1} +\ cdots +a_ {n+1})\\ &= (a_1+a_2+\ cdots +a_i) + ((a_ {i+1} +\ cdots +a_j) + (a_ {j+1} +\ cdots +a_j) + (a_ {j+1} +\ cdots +a_ {n+1})\\ & =( (a_1+a_2+\ cdots +a_i) + ((a_ {i+1} +\ cdots +a_j)) + (a_ {j+1} +\ cdots +a_ {n+1})\\ &= ((a_1+a_2+\ cdots +a_j)) + (a_ {j+1} +\ cdots a_ {n+1})\\ & ; =c_j\ quad\ quad\ cuadrado\ end {split}\ end {ecuación*}

Ejercicio\(\PageIndex{12}\)

\(S\)Sea el conjunto de todos los números que se puedan producir aplicando cualquiera de las reglas a continuación en cualquier orden un número finito de veces.

• Regla 1:\(\frac{1}{2} \in S\)
• Regla 2:\(1 \in S\)
• Regla 3: Si\(a\) y\(b\) han sido producidos por las reglas, entonces\(a b \in S\text{.}\)
• Regla 4: Si\(a\) y\(b\) han sido producidos por las reglas, entonces\(\frac{a+b}{2}\in S\text{.}\)

Demostrar que\(a\in S \Rightarrow 0 \le a \leq 1\text{.}\)

Pista

El número de veces que se aplican las reglas debe ser el número entero en el que hagas la inducción.

Ejercicio\(\PageIndex{13}\)

Las pruebas que involucran objetos que se definen recursivamente son a menudo inductivas. Una definición recursiva es similar a una prueba inductiva. Consiste en una base, generalmente la parte simple de la definición, y la recursión, que define objetos complejos en términos de simples. Por ejemplo, si\(x\) es un número real y\(n\) es un entero positivo, podemos definir de la\(x^n\) siguiente manera:

• Bases:\(x^1=x\text{.}\)
• Recursión: si\(n \geq 2\text{,}\)\(x^n= x^{n-1}x\text{.}\)

Por ejemplo,\(x^3= x^2x\) =\((x^1x)x = (x x) x\text{.}\)

Demostrar que si\(n, m \in \mathbb{P}\text{,}\)\(x^{m+n}= x^mx^n\text{.}\) Hay mucho más sobre la recursión en el Capítulo 8.

Pista

Que\(p(m)\) sea la proposición de que\(x^{m+n}= x^mx^n\) para todos\(n\geq 1\text{.}\)

Contestar

Para\(m\geqslant 1\text{,}\) dejar\(p(m)\textrm{ be } x^{n+m}=x^nx^m\) para todos\(n\geqslant 1\text{.}\) La base de esta prueba se desprende directamente de la base para la definición de exponenciación.

Inducción: Supongamos que para algunos\(m\geqslant 1, p(m)\) es cierto. Entonces

\ begin {ecuación*}\ begin {split} x^ {n+ (m+1)} & =x^ {(n+m) +1}\ quad\ textrm {por asociatividad de suma entera}\\ &=x^ {n+m} x^1\ quad\ textrm {por definición recursiva}\\ &=x^nx^mx^1\ quad\ textrm {hipótesis de inducción}\\ &=x^nx^ {m+1}\ quad\ textrm {definición recursiva}\ cuádruple\ cuadrado\ end {split}\ end { ecuación*}

Ejercicio\(\PageIndex{14}\)

Dejar\(S\) ser un conjunto finito y dejar\(P_n\) ser definido recursivamente por\(P_{1 } = S\) y\(P_n= S\times P_{n-1}\) para\(n\geq 2\text{.}\)

• Enumerar los elementos de\(P_3\) para el caso\(S = \{a, b\}\text{.}\)
• Determine la fórmula para\(\lvert P_n \rvert\text{,}\) dado eso\(\lvert S \rvert= k\text{,}\) y pruebe su fórmula por inducción.