2.1: Algunos ejemplos de introducción matemática

2.1: Inducción matemática

El principio de inducción matemática establece que

Con el fin de probar una declaración sobre un entero\(n\), si podemos

1. Demostrar la sentencia cuando\(n = b\), para algún entero fijo\(b\), y
2. Demostrar que la verdad de la declaración para\(n = k − 1\) implica la verdad de la declaración para\(n = k\) siempre\(k > b\), entonces podemos concluir que la afirmación es verdadera para todos los enteros\(n \geq b\).

Como ejemplo, demos otra prueba más de que un conjunto con\(n\) elementos tiene\(2^n\) subconjuntos. Esta prueba utiliza esencialmente las mismas bijecciones que usamos para probar la Ecuación Pascal. El enunciado que deseamos probar es el enunciado de que “Un conjunto de tamaños\(n\) tiene\(2^n\) subconjuntos”.

Nuestra declaración es verdadera cuando\(n = 0\), porque un conjunto de tamaño\(0\) es el conjunto vacío y el conjunto vacío tiene\(1 = 2^{0}\) subconjuntos. (Este paso de nuestra prueba se llama paso base.)

Ahora supongamos que\(k > 0\) y cada conjunto con\(k − 1\) elementos tiene\(2^{k−1}\) subconjuntos. Supongamos que\(S = \{a_{1}, a_{2}, \dotsi , a_{k}\}\) es un conjunto con\(k\) elementos. Particionamos los subconjuntos de\(S\) en dos bloques. Bloque\(B_{1}\) consiste en los subconjuntos que no contienen un y bloque\(B_2\) consiste en los subconjuntos que sí contienen un. Cada conjunto en\(B_{1}\) es un subconjunto de\(\{a_1, a_2, . . . a_{k−1}\}\), y cada subconjunto de\(\{a_1, a_2, . . . a_{k−1}\}\) está en\(B_{1}\). Así\(B_{1}\) es el conjunto de todos los subconjuntos de\(\{a_1, a_2, . . . a_{k−1}\}\). Por lo tanto por nuestra suposición en la primera frase de este párrafo, el tamaño de\(B_{1}\) es\(2^{k−1}\). Considere la función de\(B_{2}\) a la\(B_{1}\) que toma un subconjunto de\(S\) incluir ak y elimina ak de él. Esta función se define en\(B_{2}\), porque cada conjunto en\(B_{2}\) contiene ak. Esta función es on, porque si\(T\) es un set in\(B_{1}\), entonces\(T \cup \{ak\}\) es un conjunto en el\(B_{2}\) que la función envía a\(T\). Esta función es uno a uno porque si V y W son dos conjuntos diferentes en\(B_{2}\), entonces
eliminar ak de ellos da dos conjuntos diferentes en\(B_{1}\). Así tenemos una bijección entre\(B_{1}\) y\(B_{2}\), así\(B_{1}\) y\(B_{2}\) tenemos el mismo tamaño. Por lo tanto, por el principio de suma el tamaño de\(B_{1} \cup B_{2}\) es\(2^{k−1} + 2^{k−1} = 2^{k}\). Por lo tanto\(S\) tiene\(2^{k}\) subconjuntos. Esto muestra que si un conjunto de tamaño\(k − 1\) tiene\(2^{k−1}\) subconjuntos, entonces un conjunto de tamaño\(k\) tiene\(2^{k}\) subconjuntos. Por lo tanto, por el principio de inducción matemática, un conjunto de tamaños\(n\) tiene\(2^{n}\) subconjuntos para cada entero no negativo\(n\).

A la primera frase del último párrafo se le llama hipótesis inductiva. En una prueba inductiva siempre hacemos una hipótesis inductiva como parte de probar que la verdad de nuestra afirmación cuando\(n = k−1\) implica la verdad de nuestra afirmación cuando\(n = k\). Al último párrafo mismo se le llama el paso inductivo de nuestra prueba. En un paso inductivo derivamos la afirmación para\(n = k\) de la declaración para\(n = k−1\), demostrando así que la verdad de nuestra afirmación cuando\(n = k−1\) implica la verdad de nuestra afirmación cuando\(n = k\). A la última frase del último párrafo se le llama conclusión inductiva. Todas las pruebas inductivas deben tener un paso base, una hipótesis inductiva, un paso inductivo y una conclusión inductiva.

Hay un par de detalles que vale la pena notar. Primero, en este problema, nuestro paso base fue el caso\(n = 0\), o en otras palabras, tuvimos\(b = 0\). Sin embargo, en otras pruebas,\(b\) podría ser cualquier entero, positivo, negativo, o\(0\). En segundo lugar, nuestra prueba de que la verdad de nuestra declaración para\(n = k − 1\) implica la verdad de nuestra afirmación para que\(k\) se\(n = k\) requiera que sea al menos\(1\), para que hubiera un elemento ak que pudiéramos quitar para describir nuestra bijección. Sin embargo, la condición (2) del principio de inducción matemática solo requiere que podamos probar la implicación para\(k > 0\), por lo que se nos permitió asumir\(k > 0\).

2.1.1: Fuerte Inducción Matemática

Una forma de ver el principio de inducción matemática es que nos dice que si conocemos el “primer” caso de un teorema y podemos derivar el caso del teorema a partir de un caso menor, entonces el teorema es cierto en todos los casos. No obstante, la forma particular en que afirmamos el teorema es bastante restrictiva en cuanto nos obliga a derivar cada caso del caso inmediatamente anterior. Esta restricción no es necesaria, y eliminarla nos lleva a una afirmación más general del principio de inducción matemática que la gente suele llamar el fuerte principio de inducción matemática. Afirma:

Con el fin de probar una declaración sobre un entero\(n\) si podemos

1. Demostrar nuestra declaración cuando\(n = b\), y
2. Demostrar que las declaraciones que obtenemos con\(n = b, n = b + 1, \dotsi, n = k − 1\) implican la declaración con\(n = k\), entonces nuestra declaración es cierta para todos los enteros\(n \geq b\).

Encontrarás algunos ejemplos explícitos del uso del fuerte principio de inducción matemática en el Apéndice B y encontrarás algunos usos para ello en este capítulo.

2.1.2: Coeficientes Binomiales y Teorema Binomial

\(\bullet\) Exercise \(72\)

Cuando estudiamos la Ecuación Pascal y los subconjuntos en el Capítulo 1, puede haber aparecido que no hay conexión entre la relación Pascal\(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) y la fórmula\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\). Por supuesto que probablemente te das cuenta de que puedes probar la relación Pascal sustituyendo los valores que la fórmula te da en el lado derecho de la ecuación y simplificando para darte el lado izquierdo. De hecho, a partir de la Relación Pascal y los hechos que\(\binom{n}{j} = 1\) y\(\binom{n}{n} = 1\), en realidad se puede probar la fórmula para\(\binom{n}{k}\) por inducción en\(n\). Hazlo. (Pista).

\(\rightarrow\) Exercise \(73\)

Utilizar el hecho de que\((x + y)^{n} = (x + y)(x + y)^{n−1}\) para dar una prueba inductiva del teorema binomial. (Pista).

Ejercicio\(74\)

Supongamos que f es una función definida en los enteros no negativos tal que\(f(0) = 3\) y\(f(n) = 2f(n − 1)\). Encuentre una fórmula para\(f(n)\) y demuestre que su fórmula es correcta.

\(+\) Exercise \(75\)

Demostrar la conjetura en el Problema 13b para un entero positivo arbitrario\(m\) sin apelar al principio general del producto. (Pista).

2.1.3: Definición inductiva

Es posible que hayas visto\(n!\) descrito por las dos ecuaciones\(0! = 1\) y\(n! = n(n − 1)!\) para\(n > 0\). Por el principio de inducción matemática, sabemos que este par de ecuaciones define\(n!\) para todos los números no negativos\(n\). Por esta razón, llamamos a tal definición una definición inductiva. Una definición inductiva a veces se llama definición recursiva. A menudo podemos obtener pruebas muy fáciles de hechos útiles mediante el uso de definiciones inductivas.

\(\rightarrow\) Exercise \(76\)

Una definición inductiva de\(a^{n}\) para no negativo\(n\) viene dada por\(a^{0} = 1\) y\(a^{n} = aa^{n−1}\). (Observe la similitud con la definición inductiva de\) (n! \).) Hemos comentado anteriormente que las definiciones inductivas a menudo nos dan pruebas fáciles de hechos útiles. Aquí aplicamos esta definición inductiva para probar dos datos útiles sobre los exponentes que has estado usando casi desde que aprendiste el significado de los exponentes.

1. Utilice esta definición para probar la regla de exponentes\(a^{m+n} = a^{m}a^{n}\) para no negativos\(m\) y\(n\). (Pista).
2. Usa esta definición para probar la regla de los exponentes\(a^{mn} = (a^{m})^{n}\). (Pista).

\(+\) Exercise \(77\)

Supongamos que\(f\) es una función sobre los enteros no negativos tal que\(f(0) = 0\) y\(f(n) = n + f(n − 1)\). \(f(n) = n(n + 1)/2\)Demuéstralo. Observe que esto da una tercera prueba de que\(1 + 2 + \dotsi + n = n(n + 1)/2\), debido a que esta suma satisface las dos condiciones para\(f\). (La suma no tiene términos y es así\(0\) cuándo\(n = 0\).)

\(\rightarrow\) Exercise \(78\)

Dar una definición inductiva de la notación de suma\(\sum^{n}_{i=1}a_{i}\). Utilízala y la ley distributiva\(b(a + c) = ba + bc\) para acreditar la ley distributiva\[b\sum_{i=1}^{n} a_i = \sum^{n}_{i=1}ba_{i}.\]

2.1.4: Demostrar el Principio General del Producto (Opcional)

Declaramos el principio de suma como

Si tenemos una partición de un conjunto finito\(S\), entonces el tamaño de\(S\) es la suma de los tamaños de los bloques de la partición.

De hecho, la forma más simple del principio de suma dice que el tamaño de la suma de dos conjuntos disjuntos (finitos) es la suma de sus tamaños.

Ejercicio\(79\)

Demostrar el principio de suma que declaramos para particiones de un conjunto a partir de la forma más simple del principio de suma. (Pista).

Declaramos la forma de partición del principio del producto como

Si tenemos una partición de un conjunto finito\(S\) en\(m\) bloques, cada uno de tamaño\(n\), entonces\(S\) tiene tamaño\(mn\).

En el Problema 11 dimos una forma más general del principio del producto que se puede afirmar como

Si hacemos una secuencia de\(m\) elecciones para las cuales

• hay\(k_{1}\) posibles primeras opciones, y
• para cada forma de tomar las primeras\(i − 1\) decisiones, hay\(k_{i}\)
  formas de hacer la\(i^{\text{th}}\) elección,

entonces podemos hacer nuestra secuencia\(Q\) de elecciones de\(k_{1} \cdot k_{2} \dotsi \dotsi k_{m} = \prod^{m}_{i=1}k_{i}\) maneras.

En el Problema 14 afirmamos el principio general del producto de la siguiente manera.

Dejar\(S\) ser un conjunto de funciones\(f\) de\([n]\) a algún conjunto\(X\). Supongamos que

• hay\(k_{1}\) opciones para\(f(1)\), y
• para cada elección de\(f(1), f(2), \dotsc, f(i − 1)\), hay\(k_{i}\) opciones para\(f(i)\).

Entonces el número de funciones en el conjunto\(S\) es\(k_{1}k_{2} \dotsi k_{n}\).

Puede utilizar cualquier forma de afirmar el principio general del producto en el siguiente Problema.

\(+\) Exercise \(80\)

Demostrar la forma general del principio del producto a partir de la forma de partición del principio del producto. (Pista).

2.1.5: Doble Inducción y Números Ramsey

En la Sección 1.3.4 dimos dos descripciones distintas del número Ramsey\(R(m, n)\). No obstante, si miras con atención, verás que nunca demostramos que los números de Ramsey realmente existen; simplemente describimos lo que eran y lo demostramos\(R(3, 3)\) y\(R(3, 4)\) existimos calculándolos directamente. Siempre y cuando podamos demostrar que hay algún número\(R\) tal que cuando hay\(R\) personas juntas, hay conocidos\(m\) mutuos o extraños\(n\) mutuos, esto demuestra que el Número Ramsey\(R(m, n)\) existe, porque es el más pequeño de este tipo\(R\). La inducción matemática nos permite demostrar que uno de esos\(R\) es\(\binom{m+n-2}{m-1}\). La pregunta es, ¿en qué debemos inducir,\(m\) o\(n\)? Es decir, ¿usamos el hecho de que con\(\binom{m+n-3}{m-2}\) personas en una habitación hay al menos conocidos\(m−1\) mutuos o extraños\(n\) mutuos, o usamos el hecho de que con al menos\(\binom{m+n-3}{m-2}\) personas en una habitación hay al menos conocidos\(m\) mutuos o al menos\(n − 1\) extraños mutuos? Resulta que usamos ambos. Así queremos ser capaces de inducir simultáneamente en\(m\) y\(n\). Una forma de hacerlo es usar otra variación del principio de inducción matemática, el Principio de Doble Inducción Matemática. Este principio (que puede derivarse de uno de nuestros anteriores) establece que

Con el fin de probar una declaración sobre enteros\(m\) y\(n\), si podemos

1. Demostrar la sentencia cuándo\(m = a\) y\(n = b\), para enteros fijos\(a\) y\(b\)
2. Demostrar la declaración cuándo\(m = a\)\(n > b\)\(m > a\) y cuándo y\(n = b\) (para los mismos enteros fijos\(a\) y\(b\)),
3. Demostrar que la verdad de la declaración para\(m = j\) y\(n = k − 1\) (con j a y k > j) y la verdad de la declaración para\(m = j − 1\) y\(n = k\) (con\(j > a\) y\(k \geq b\)) implican la verdad de la declaración para\(m = j\) y\(n = k\),

entonces podemos concluir que la sentencia es verdadera para todos los pares de enteros\(m \geq a\) y\(n \geq b\).

Hay una versión fuerte de doble inducción, y en realidad es más fácil de afirmar. El principio de inducción matemática doble fuerte dice lo siguiente.

Con el fin de probar una declaración sobre enteros\(m\) y\(n\), si podemos

1. Demostrar la sentencia cuando\(m = a\) y\(n = b\), para enteros fijos\(a\) y\(b\).
2. Demostrar que la verdad de la declaración para los valores de\(m\) y\(n\) con\(a + b \leq m + n < k\) implica la verdad de la declaración para\(m + n = k\),

entonces podemos concluir que la afirmación es verdadera para todos los pares de enteros\(m \geq a\) y\(n \geq b\).

\(\rightarrow \; \cdot\) Exercise \(81\)

Demostrar que eso\(R(m, n)\) existe demostrando que si hay\(\binom{m+n+2}{m-1}\) gente en una habitación, entonces hay al menos conocidos\(m\) mutuos o al menos extraños\(n\) mutuos. (Pista).

Ejercicio\(82\)

\(R(m, n) \leq R(m − 1, n) + R(m, n − 1)\)Demuéstralo. (Pista).

Ejercicio\(83\)

1. ¿De qué nos habla la ecuación del Problema 82\(R(4, 4)\)?
2. Considera a\(17\) las personas dispuestas en un círculo de tal manera que cada persona conozca a la primera, segunda, cuarta y octava persona a la derecha y la primera, segunda, cuarta y octava persona a la izquierda. ¿Puedes encontrar un conjunto de cuatro conocidos mutuos? ¿Puedes encontrar un conjunto de cuatro desconocidos mutuos? (Pista).
3. ¿Qué es\(R(4, 4)\)?

Ejercicio\(84\)

(Opcional) Demostrar la desigualdad del Problema 81 por inducción sobre\(m+n\).

Ejercicio\(85\)

Usa la aproximación de Stirling (Problema 46) para convertir el límite superior para el\(R(n, n)\) que obtienes del Problema 81 a un múltiplo de una potencia de un entero.

2.1.6: Un poco de combinatoria asintótica

El problema 85 nos da un límite superior encendido\(R(n, n)\). Una técnica muy inteligente debido a Paul Erdös, llamada el “método probabilístico”, dará un límite inferior. Dado que ambos límites son exponenciales en\(n\), muestran que\(R(n, n)\) crece exponencialmente a medida que\(n\) se agranda. Un análisis de lo que sucede con una función de\(n\) como\(n\) se agranda suele llamarse análisis asintótico. El método probabilístico, al menos en sus formas más simples, puede expresarse en términos de promedios, por lo que no es necesario conocer el lenguaje de la probabilidad para poder entenderlo. Lo aplicaremos a números Ramsey en el próximo problema. Combinado con el resultado del Problema 85, este problema nos va a dar eso\(\sqrt{2}^{n} < R(n, n) < 2^{2n−2}\), para que sepamos que el número de Ramsey\(R(n, n)\) crece exponencialmente con\(n\).

\(\rightarrow\) Exercise \(86\)

Supongamos que tenemos dos números\(n\) y\(m\). Consideramos todas las formas posibles de colorear los bordes de la gráfica completa\(K_{m}\) con dos colores, digamos rojo y azul. Para cada coloración, observamos cada subconjunto\(n\) -elemento\(N\) del conjunto de vértices\(M\) de\(K_{m}\). Luego\(N\) junto con los bordes de los vértices de\(K_{m}\) conexión en\(N\) formas una gráfica completa sobre\(n\) los vértices. Esta gráfica, que denotamos por\(K_{N}\), tiene sus bordes coloreados por la coloración original de los bordes de\(K_{m}\).

1. ¿Por qué es eso, si no hay subconjunto\(N \subseteq M\) para que todos los bordes de\(K_{N}\) estén coloreados del mismo color para cualquier coloración de los bordes de\(K_{m}\), entonces\(R(n, n) > m\)? (Pista).
2. Para aplicar el método probabilístico, vamos a calcular el promedio, sobre todos los colorantes de\(K_{m}\), del número de conjuntos\(N \subseteq M\) con\(|N| = n\) tal que\(K_{N}\) sí tiene todos sus bordes del mismo color. Explique por qué es que si el promedio es menor que\(1\), entonces para alguna coloración no hay conjunto\(N\) tal que\(K_{N}\) tenga todos sus bordes coloreados del mismo color. ¿Por qué esto significa eso\(R(n, n) > m\)? (Pista).
3. Llamamos a\(K_{N}\) monocromática para una coloración\(c\) de\(K_{m}\) si el color\(c(e)\) asignado al borde\(e\) es el mismo para cada borde e de\(K_{N}\). Definamos mono (\(c,N\)) para ser\(1\) si\(N\) es monocromático para\(c\) y ser de\(0\) otra manera. Encuentre una fórmula para el número promedio de\(K_{N}\) s monocromáticas sobre todos los colorantes\(K_{m}\) que implica una doble suma primero sobre todos los colores de borde\(c\) de\(K_{m}\) y luego sobre todos los subconjuntos\(N \subseteq M\) de\(n\) elementos de\(mono(c,N\)). (Pista).
4. Demuestre que su fórmula para el promedio se reduce a\(2\binom{m}{n} \cdot 2^{-\binom{n}{2}}\) (Pista).
5. Explique por qué\(R(n, n) > m\) si\(\binom{m}{n} \leq 2^{\binom{n}{2} - 1}\). (Pista).
6. *Explica por qué\(R(n,n) > \sqrt[n]{n!2^{\binom{n}{2} - 1}}\). (Pista).
7. Al usar la fórmula de Stirling, demuestre que si\(n\) es lo suficientemente grande, entonces\(R(n,n) > \sqrt{2^{n}} = \sqrt{2}^{n}\). (Aquí lo suficientemente grande significa lo suficientemente grande como
   para que la fórmula de Stirling sea razonablemente precisa).