Apéndice B: Inducción matemática

B.1.1: Las ideas detrás de la inducción matemática

Hay una variante de una de las becciones que usamos para probar la Ecuación Pascal que surge al contar los subconjuntos de un conjunto. En el siguiente problema, nos ayudará a calcular el número total de subconjuntos de un conjunto, independientemente de su tamaño. Nuestro principal objetivo en este problema, sin embargo, es introducir algunas ideas que nos conduzcan a una de las técnicas de prueba más poderosas en combinatoria (y muchas otras ramas de las matemáticas), el principio de inducción matemática.

En los Problemas 360 y 361, nuestras pruebas tenían varios elementos distintos. Teníamos una declaración que involucraba a un entero\(n\). Sabíamos que la afirmación era cierta para los primeros enteros no negativos en el Problema 360 y para los primeros enteros positivos en el Problema 361. Queríamos probar que la afirmación era cierta para todos los enteros no negativos en el Problema 360 y para todos los enteros positivos en el Problema 361. En ambos casos utilizamos el método de prueba por contradicción; para ello asumimos que había un valor\(n\) para el que nuestra fórmula no era cierta. Entonces elegimos\(k\) ser el valor más pequeño\(n\) para el cual nuestra fórmula no era cierta. Esto significaba que cuando\(n\) era\(k − 1\), nuestra fórmula era verdadera, (o de lo contrario eso no\(k − 1\) era un entero no negativo en el Problema 360 o que no\(k − 1\) era un entero positivo en el Problema 361). Lo que hicimos a continuación fue el quid de la prueba. Demostramos que la verdad de nuestra declaración para\(n = k −1\) implicaba la verdad de nuestra declaración para\(n = k\). Esto nos dio una contradicción con el supuesto de que había una\(n\) que hacía falsa la declaración. De hecho, veremos que podemos eludir por completo el uso de la prueba por contradicción. Lo usamos para ayudarte a descubrir las ideas centrales de la técnica de la prueba por inducción matemática.

El núcleo central de la inducción matemática es la prueba de que la verdad de una afirmación sobre el entero\(n\) para\(n = k − 1\) implica la verdad de la afirmación para\(n = k\). Por ejemplo, una vez que sabemos que un conjunto de tamaño\(0\) tiene\(2^0\) subconjuntos, si hemos demostrado nuestra implicación, entonces podemos concluir que un conjunto de tamaño\(1\) tiene\(2^1\) subconjuntos, de los cuales podemos concluir que un conjunto de tamaño\(2\) tiene\(2^2\) subconjuntos, de los cuales podemos concluir que un conjunto de tamaño\(3\) tiene\(2^3\) subconjuntos, y así sucesivamente hasta un conjunto de tamaño\(n\) que tiene\(2^n\) subconjuntos para cualquier entero no negativo\(n\) que elijamos. Es decir, aunque fue la idea de prueba por contradicción lo que nos llevó a pensar en tal implicación, ahora podemos prescindir de la contradicción en absoluto. Lo que necesitamos para probar una afirmación\(n\) por este método es un lugar para comenzar, ese es un valor\(b\)\(n\) para el que sabemos que la afirmación es cierta, y luego una prueba de que la verdad de nuestra declaración para\(n = k − 1\) implica la verdad de la declaración para\(n = k\) siempre que \(k > b\).

B.1.2: Inducción Matemática

El principio de inducción matemática establece que:

Para probar una declaración sobre un entero\(n\), si podemos

1. Demostrar la sentencia cuando\(n = b\), para algún entero fijo\(b\)
2. Demostrar que la verdad de la declaración para\(n = k −1\) implica la verdad de la declaración para\(n = k\) cuando\(k > b\),

entonces podemos concluir que la sentencia es verdadera para todos los enteros\(n ≥ b\). Como ejemplo, volvamos al Problema 360. El enunciado que deseamos probar es el enunciado de que “Un conjunto de tamaños\(n\) tiene\(2n\) 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,... a_k \}\) es un conjunto con\(k\) elementos. Partituramos 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\(a_n\). 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 un y elimina\(a_n\) de ella. Esta función se define en\(B_2\), porque cada conjunto en\(B_2\) contiene\(a_n\). Esta función es on, porque si\(T\) es un set in\(B_1\), entonces\(T ∪ \{a_k \}\) 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\), luego quitarlos\(a_k\) de ellos da dos conjuntos diferentes en\(B_1\). Así tenemos una bection 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 ∪ B_2\) es\(2^{k−1} + 2^{k−1} = 2k\). 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 que\(a_k\) pudiéramos quitar para describir nuestra becció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\).

B.1.3: Demostrar declaraciones algebraicas por inducción

B.1.4: Inducción Fuerte

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:

Para 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,... n = k−1\) implican la declaración con\(n = k\),

entonces nuestra afirmación es verdadera para todos los enteros\(n ≥ b\).

Probablemente veas que podemos hacer n centavos en franqueo siempre y cuando\(n\) sea por lo menos\(20\). Sin embargo, no intentaste hacer\(26\) centavos en franqueo trabajando con\(25\) centavos; más bien viste que podías conseguir\(20\) centavos y luego sumar seis centavos a eso para obtener\(26\) centavos. Así, si queremos demostrar por inducción que tenemos razón en que si\(n ≥ 20\), entonces podemos hacer\(n\) centavos de franqueo, vamos a tener que usar la versión fuerte del principio de inducción matemática.

Sabemos que podemos hacer\(20\) centavos con cuatro sellos de cinco centavos. Ahora dejamos\(k\) ser un número mayor que\(20\), y supongamos que es posible hacer cualquier cantidad entre\(20\) y\(k − 1\) centavos en franqueo con sellos de cinco y seis centavos. Ahora si\(k\) es menor que\(25\), es\(21\),\(22\),\(23\), o\(24\). Podemos hacer\(21\) con tres cincos y uno seis. Podemos hacer\(22\) con dos cincos y dos seis,\(23\) con uno cinco y tres seis, y\(24\) con cuatro seis. De lo contrario,\(k − 5\) es entre\(20\) y\(k − 1\) (inclusivo) y así por nuestra hipótesis inductiva, sabemos que los\(k − 5\) centavos se pueden hacer con sellos de cinco y seis centavos, así con un sello más de cinco centavos, también los\(k\) centavos. Así, por el (fuerte) principio de inducción matemática, podemos hacer\(n\) centavos en sellos con sellos de cinco y seis centavos para cada uno\(n ≥ 20\).

Algunas personas podrían decir que realmente teníamos cinco casos base,\(n = 20\),\(21\),\(22\),\(23\), y\(24\), en la prueba anterior y una vez que hubiéramos probado esos cinco casos base consecutivos, entonces podríamos reducir cualquier otro caso a uno de estos casos base restando sucesivamente\(5\). Esa es una forma apropiada de ver la prueba. Un lógico diría que también es el caso que, por ejemplo, al probar que podríamos hacer\(22\) centavos, también probamos que si podemos hacer\(20\) centavos y\(21\) centavos en sellos, entonces también podríamos hacer\(22\) centavos. ¡Simplemente no nos molestamos en usar la suposición de que podíamos ganar\(20\) centavos y\(21\) centavos! En tanto que un punto de vista u otro te satisfaga, estás listo para usar este tipo de argumentos en pruebas.