¿Cuál es el segundo principio de la inducción finita?

Question

Entiendo el principio de inducción finita, pero mi libro menciona entonces que hay una variante de la primera en la que el requisito b se cambia por

Si $k$ es un número entero positivo tal que $1,2, \dots, k$ pertenecen a $S$ entonces $k + 1$ también debe estar en $S$ .

El problema de la muestra es demostrar que la desigualdad sobre los números de Lucas $l_n < (7/4)^n$ .
Entiendo el álgebra de la prueba, pero no entiendo cómo utiliza el segundo principio o en qué se diferencia del primer principio

La prueba de los números lucas $$ a_1 = 1 < \left(\frac{7}{4}\right)^1 = \frac{7}{4}\text{ and }a_2 = 3 \lt \left(\frac{7}{4}\right)^2 = \frac{49}{16}.$$

Elija un número entero $k\geq 3$ y asumir que la desigualdad es válida para $n = 1,2,\ldots,k$ . Entonces

$$a_{k-1} \lt \left(\frac{7}{4}\right)^{k-1}\text{ and }a_{k-2} \lt \left(\frac{7}{4}\right)^{k-2},$$ así que \begin {align*} a_k &= a_{k-1} + a_{k-2} \\\ & \lt \left ( \frac {7}{4} \right )^{k-1} + \left ( \frac {7}{4} \right )^{k-2} \\\ &= \left ( \frac {7}{4} \right )^{k-2} \left ( \frac {7}{4} + 1 \right ) \\\ &= \left ( \frac {7}{4} \right )^{k-2} \left ( \frac {11}{4} \right ) \\\ & \lt \left ( \frac {7}{4} \right )^{k-2} \left ( \frac {7}{4} \right )^2 \\\ &= \left ( \frac {7}{4} \right )^k \end {align*}

Las respuestas son todas útiles, pero si alguien pudiera señalar cuál es la diferencia cuando se utiliza realmente la inducción fuerte en lugar de la inducción débil. (Se podría utilizar la prueba del número de Lucas o alguna otra cosa)

Answer 1

Hay dos diferencias básicas:

• En la inducción ordinaria, necesitamos un caso base (probándolo para $k=1$ es decir, demostrar que $1\in S$ ); en el segundo principio de inducción (también llamado "inducción fuerte") no se necesita un caso base (pero véase el advertencia abajo).

• En la inducción ordinaria, la "hipótesis de inducción" es que la $k\in S$ En el segundo principio, la "Hipótesis de Inducción" es que todo los números naturales estrictamente menores que $k+1$ están en $S$ .

Por ejemplo, si se quiere demostrar que todo entero positivo puede ser factorizado en primos, si se utiliza la inducción ordinaria habría que demostrar primero que $1$ se puede factorizar en primos, y entonces se demostraría que si $k$ puede ser factorizado en primos, entonces $k+1$ puede ser factorizado en primos. En realidad, esto es bastante difícil de hacer, porque la factorización de $k+1$ tiene poco o nada que ver con la factorización de $k$ . Esta es una proposición muy difícil de demostrar directamente utilizando la inducción ordinaria.

Si quisieras demostrar la misma proposición utilizando el segundo principio de inducción, asumirías que todo números estrictamente inferiores a $k$ puede ser factorizado en primos, y tratar de demostrar a partir de esta suposición que $k$ se puede factorizar en primos (lo que es mucho más sencillo: si $k=1$ o $k$ es primo, no hay nada que hacer; si no, se puede escribir $k=ab$ Cada uno de ellos $a$ o $b$ estrictamente menor que $k$ y mayor que $1$ , por lo que se puede aplicar la hipótesis de inducción a ambos para obtener una factorización).

En otras palabras, en el segundo principio, se llega a asumir más en el paso inductivo.

Advertencia: Formalmente, el segundo principio no requiere una base porque si se puede demostrar que "si todos los enteros positivos son estrictamente menores que $k$ están en $S$ entonces $k$ está en $S$ ", entonces para $k=1$ la premisa es vacuamente cierta ( todo número entero positivo menor que $1$ son en $S$ porque no existe tal número), por lo que la implicación sería que $k=1$ también debe estar en $S$ . Sin embargo, en la mayoría de las aplicaciones reales, el argumento inductivo no funciona para $k=1$ (o para otros casos especiales), por lo que hay que demostrarlos por separado. Se trata de "casos especiales" en lugar de "bases".

De hecho, ambos principios son equivalente para los enteros positivos. Es decir, si se puede hacer una demostración utilizando la inducción ordinaria, entonces se puede traducir en una demostración utilizando el segundo principio de inducción de una manera bastante mecánica. Y si se puede hacer una demostración utilizando el segundo principio de inducción, se puede transformar en una demostración utilizando el primer principio de inducción (aunque de forma indirecta), de nuevo de forma bastante mecánica (siempre que se den por supuestas algunas propiedades de los enteros positivos; por ejemplo, que todo entero positivo es o bien igual a $1$ , o bien es $k+1$ para algún número entero positivo $k$ ).

Nota: La razón por la que el segundo principio se llama "inducción fuerte" es que se puede utilizar en otros contextos para demostrar más de lo que haría la inducción ordinaria. Por ejemplo, imagina una situación en la que tienes un conjunto $T$ que consiste en dos copias de los enteros: una copia azul y una copia verde, y la copia azul va "primero". Si se demuestra que $S$ es un subconjunto de $T$ tal que el azul $1$ está en $S$ y siempre que $k$ ( $k$ un número entero positivo azul o un número entero positivo verde) está en $S$ entonces $k+1$ está en $S$ (inducción ordinaria), entonces se puede concluir que todos los enteros azules están en $S$ pero el argumento por sí mismo no te dice si hay algún entero verde en $S$ (tendría que demostrar por separado que el verde- $1$ está en $S$ ). Pero si se utiliza la inducción fuerte, y se demuestra que siempre que todos los enteros, azules o verdes, que son estrictamente menores que $k$ están en $S$ entonces $k$ está en $S$ Entonces, usted puede concluir que $S$ contendrá todos los enteros azules y todos los enteros verdes también. Así que puedes obtener un más fuerte conclusión del uso de la inducción fuerte.

Advertencia la segunda : Los casos especiales aparecen mucho más a menudo en las pruebas que utilizan la inducción fuerte que en las pruebas que utilizan la inducción ordinaria, pero a veces también se dan en estas últimas. Un ejemplo famoso de una "prueba" que utiliza la inducción ordinaria y que requeriría un caso especial (y que de hecho es falsa porque ese caso especial falla) es la falsa prueba de la proposición de que "Si, en un grupo de personas, al menos una de ellas tiene los ojos azules, entonces todos en el grupo tienen los ojos azules". La prueba es la siguiente: Sea $k$ denotan el número de personas en el grupo. Lo demostramos por inducción en $k$ . Si $k=1$ entonces el resultado se mantiene obviamente. Supongamos que el resultado es válido para cualquier grupo con $k$ personas, y tomar un grupo con $k+1$ personas, $(p_1,\ldots,p_{k},p_{k+1})$ en el que al menos uno tiene los ojos azules, digamos $p_1$ . Mirando la primera $k$ , $(p_1,\ldots,p_k)$ podemos utilizar la hipótesis de inducción para concluir que $p_1,p_2,\ldots,p_k$ cada uno tiene ojos azules. Entonces, mirando al último $k$ , $(p_2,\ldots,p_k,p_{k+1})$ ya que al menos uno tiene los ojos azules (digamos $p_k$ ), entonces todos tienen ojos azules por la hipótesis de la inducción. En particular, $p_{k+1}$ tiene los ojos azules. Por lo tanto, todos tienen ojos azules, QED.

La razón por la que esto está incompleto es que el paso inductivo sólo funciona si $k\geq 3$ de modo que una prueba requeriría la caso especial de demostrar que $1\in S$ implica $2\in S$ (el argumento general que tenemos no cubre esa implicación particular). Ahí es donde se rompe todo, por supuesto. Pero la cuestión es que a veces la inducción ordinaria también requiere "casos especiales", aunque esto suele ocurrir con menos frecuencia que con la inducción fuerte.

---

El paso en el que se utiliza la hipótesis inductiva en la prueba anterior es en la segunda línea de la pantalla larga, donde se utiliza que la desigualdad que se desea se mantiene para ambos $a_{k-1}$ y para $a_{k-2}$ . Para ello hay que suponer que se cumple para dos números estrictamente menores que $k$ (no es necesario el hecho de que se mantenga para todo números inferiores a $k$ aquí, pero acabas necesitándolo para algo más que lo inmediatamente anterior).

En la inducción regular, su única suposición es que el resultado es válido para el número inmediatamente anterior (para $k-1$ cuando se trata de probarlo para $k$ o para $k$ cuando se trata de probarlo para $k+1$ ). No hace ninguna suposición sobre lo que ocurre para $\ell$ con $\ell\lt k-1$ . En la inducción fuerte, se asume que se mantiene para todo $\ell\lt k$ no sólo para $k-1$ . Aquí, porque se necesita el supuesto para dos los valores más pequeños de $k$ Este argumento no funcionaría si sólo se asumiera que $a_{k-1}\lt\left(\frac{7}{4}\right)^{k-1}$ pero no hacían suposiciones sobre $a_{k-2}$ . Allí son formas de demostrar el resultado utilizando la inducción ordinaria, pero este argumento en particular no funcionaría.

Observe que como su prueba requiere que tenga al menos dos valores menores que $k$ el argumento no funcionará para ninguno de los dos $k=1$ o $k=2$ (el primero no tiene valores menores, el segundo sólo tiene uno); por eso se acaba teniendo que demostrar la dos casos especiales de $a_1$ y $a_2$ . De nuevo, no se trata de una "base para la inducción", sino de casos especiales del argumento inductivo.

Answer 2

No es un buen ejemplo. Este principio suele tener el nombre de fuerte inducción La cuestión es que, aunque es equivalente a la inducción ordinaria, a menudo es más conveniente utilizarla en las pruebas. Para demostrar una secuencia $P(k)$ de identidades, a menudo es sencillo escribir $P(k+1)$ en términos de $P(k)$ pero para una secuencia de afirmaciones más complicada se podría necesitar la suposición más fuerte de que $P(1), ... P(k)$ todo se sostiene para poder deducir fácilmente $P(k+1)$ .

Por ejemplo, si uno está probando una secuencia de declaraciones $P(k)$ acerca de lo finito gráficos con $k$ vértices, una estrategia de prueba general es dividir un gráfico en dos gráficos más pequeños, y si la afirmación para cada uno de los gráficos más pequeños implica la afirmación para el gráfico más grande, hemos terminado por inducción fuerte, pero no necesariamente por inducción débil, ya que los gráficos más pequeños no tienen necesariamente tamaños $1$ y $k-1$ .

Como otro ejemplo, he aquí un bonito ejercicio. Considere la secuencia $a_n$ con $a_1 = 1$ y

$$a_{2n} = a_n$$ $$a_{2n+1} = a_n + 1.$$

Intenta demostrar por inducción fuerte que $a_n$ es la suma de los dígitos de $n$ en la base $2$ . ¿Puedes ver por qué esta prueba es difícil de enunciar usando la inducción débil?

Answer 3

Existe la idea errónea de que la inducción fuerte es de alguna manera "más fuerte" que la inducción normal, pero en realidad no lo es. La inducción fuerte no es más que el caso especial de la inducción normal en el que la hipótesis de inducción $P(n)$ tiene la forma "para todos $m < n$ , $Q(m)$ ". Así, la inducción fuerte es en realidad una limitado forma del principio de inducción, porque no todas las hipótesis de inducción son de esa forma especial. Por otra parte, cualquier prueba por inducción fuerte puede reformularse trivialmente como una prueba por inducción "débil".

Una de las razones de la dificultad terminológica es que el único lugar donde se habla de "inducción fuerte" es en los cursos de introducción. Allí, "utilizar la inducción fuerte" puede ser una pista sobre qué tipo de hipótesis de inducción elegir. En estas clases, el principio de inducción se enuncia de manera un tanto informal, por lo que puede no ser obvio lo que cuenta como una hipótesis de inducción legal en primer lugar.

En los contextos en los que el principio de inducción se enuncia formalmente, por ejemplo la aritmética de Peano, nadie habla de la inducción fuerte. El esquema axiomático para la inducción en la aritmética de Peano incluye simplemente todos los axiomas de la forma $$ (P(0) \land (\forall n)(P(n) \to P(n+1)) \to (\forall n)(P(n)) $$ donde $P$ es cualquier fórmula de la aritmética de Peano. Esto incluye fórmulas de la forma $(m < n)\to Q(m)$ así como todas las demás fórmulas.

Answer 4

El segundo principio de inducción al que te refieres se llama a veces principio fuerte de inducción, en contraposición al habitual, que también se llama a veces principio débil de inducción. Esta distinción sólo es aparente al principio, ya que ambos son equivalentes, por lo que no hay ningún inconveniente en utilizar la versión fuerte del mismo y pensar que se está utilizando algo mucho más potente.

Como puede ver en este Correo electrónico: La diferencia es, básicamente, que en el principio débil de inducción, tu hipótesis inductiva es simplemente que la propiedad que quieres demostrar es verdadera para algún número entero $n$ y luego demuestras que también es válida para $n+1$ .

Pero en la versión fuerte se asume que la propiedad se mantiene para todos los enteros hasta $n$ es decir, se supone que es válida para $0, 1, 2, \dots , n$ .

Un ejemplo de teorema que a veces se demuestra utilizando la versión fuerte es el llamado Teorema fundamental de la aritmética . El teorema consiste básicamente en dos partes, una es mostrar la existencia de una factorización en primos y la otra es mostrar que "la" factorización es única. Así que, por ejemplo, si estás demostrando que existe una factorización por inducción, entonces en el paso inductivo tendrás que demostrar que si $n$ puede ser factorizado como un producto de primos, el así puede $n+1$ .

El problema ahora es que tienes básicamente dos opciones, que $n+1$ es un primo en cuyo caso has terminado, o que $n+1$ es compuesto, por lo que se puede factorizar como $n+1 = ab$ donde $1 < a \leq n$ y $1 < b \leq n$ . Ahora puedes ver donde el principio fuerte es útil porque si asumes no sólo que $n$ puede ser factorizado como un producto de primos, pero también que todos los enteros mayores que $1$ puede (hasta $n$ por supuesto), entonces usted sabe inmediatamente que ambos $a$ y $b$ son productos de primos, digamos $a = p_1 \cdots p_k$ y $b = q_1 \cdots q_s$ con $p_i$ y $q_j$ primos, entonces $n+1 = ab = p_1 \cdots p_k \cdot q_1 \cdots q_s$ también es un producto de primos, por lo que la inducción es completa.