¿Cuál es el beneficio de usar una inducción fuerte cuando es reemplazable por una inducción débil?

Question

Los dos tipos de inducciones tienen proceso de la prueba de la P(a) y "para todos los enteros $n \ge b, P(n)$" como un resultado en común.

Por ejemplo, en la prueba de la siguiente pregunta, podemos utilizar débil de inducción en lugar de fuerte inducción, y el uso débil(ordinario) de la inducción hace que la prueba más simple y más corta que la forma fuerte de inducción. ¿Cuál es el beneficio del uso de la fuerte inducción cuando es sustituible por la debilidad de la inducción?

[EDITAR] Conforme a lo solicitado, aquí está la débil inducción versión de la pregunta. Además, he cambiado el $s{k_1}$ parte en rojo en la debilidad de la inducción después de leer las respuestas. Ahora entiendo demostrando a los débiles de la inducción no es prueba de la declaración.

FYI Ejemplo de una prueba de un teorema de uso débil(ordinario) de la inducción
Fuente: Matemáticas Discretas con las Aplicaciones, Susanna S. Epp

Answer 1

Las otras dos respuestas son, por supuesto, correcto, pero teniendo en cuenta sus comentarios sobre Brian por la respuesta, voy a dar una más abajo-a-tierra de respuesta: con toda probabilidad, la prueba de que usted tiene en mente utilizar débil de la inducción no es correcto. Usted debe hacer como Git Gud dice y escribe exactamente ¿qué alternativas de la prueba de que usted tiene en mente.

¿Por qué sospecho que usted no tiene una débil prueba de la afirmación de la Ppe prueba? Porque, como Brian ilustra, si usted toma el $P(n)$ a ser la declaración de $$s_n=5^n-1$$ usted no puede mostrar $P(k+1)$ únicamente sobre la base de $P(k)$.

Por qué? Sólo probarlo. Por definición, $$s_{k+1}=6s_k-5s_{k-1}$$ y por la hipótesis de $P(k)$, podemos sustituir el $5^k-1$$s_k$, por lo que tenemos $$s_{k+1}=6(5^k-1)-5\color{blue}{s_{k-1}}$$ Pero, ¿qué hacemos con $s_{k-1}$? No tenemos ninguna hipótesis sobre ella! Sólo si utilizamos fuerte inducción, podemos utilizar la hipótesis de $P(k-1)$ y así sustituir en $5^{k-1}-1$$s_{k-1}$.

Answer 2

En el ejemplo que estamos discutiendo, puede no dejar fuera demostrando $P(1)$. Para ver esto, cambiar la definición de la secuencia ligeramente: $s_0=0$, $s_1=5$, y $s_k=6s_{k-1}-5s_{k-2}$$k\ge 2$. Como antes, vamos a $P(n)$ ser la fórmula $s_n=5^n-1$. A continuación, $P(0)$ es cierto, y la inducción de paso se procede exactamente igual que antes, para mostrar que si $P(i)$ es verdadera para todos los enteros $i$ $0$ a través de $k$, e $k\ge 1$, a continuación, $P(k+1)$ es cierto: no hay nada en esa parte del argumento de que depende el valor de $s_1$. Sin embargo, es obvio que no es el caso que $P(n)$ es verdadera para todos los enteros $n\ge 0$, ya que el $P(1)$ es falso.

La inducción paso requiere saber que $P(k)$ e $P(k-1)$ son verdaderas: sin los dos, no se puede derivar la verdad de $P(k+1)$. Y eso significa que, para obtener $P(2)$, usted necesita saber no sólo que $P(0)$ es verdad, pero también que $P(1)$ es cierto. Por lo tanto, este argumento realmente hace uso fuerte de inducción.

De hecho, las dos formas de inducción son lógicamente equivalentes, y cada argumento en el uso fuerte de inducción se puede convertir a uno en el que los usos ordinarios de la inducción, pero la conversión se requiere el cambio de la proposición $P$. No recuerdo si Ppe demuestra la equivalencia; si no, dejar una pregunta, y voy a explicar más.

En la práctica uno simplemente usa cualquier forma de inducción es conveniente. Realmente deseo que de primaria textos no hacer una gran cosa de la diferencia: no es realmente muy importante, aparte del hecho de que el llamado fuerte de inducción es en muchos sentidos una mejor introducción a formas más sofisticadas de la inducción como estructurales y de inducción transfinita.

Answer 3

Fuerte de Inducción es más intuitivo en lugares donde uno no sabe de antemano para que el valor de uno tendrá la hipótesis de inducción.

Considerar la reclamación:

Cada entero $n \ge 2$ es divisible por un número primo.

El uso de una fuerte inducción de la prueba es sencilla. Es cierto para $n=2$ $2 \mid 2$ $2$ es primo.

Supongamos que la instrucción cierto para $2 \le a \le n$. Mostramos $n+1$ es divisible por un número primo.

Si $n+1$ es un número primo, entonces como $(n+1) \mid (n+1)$, la demanda está probado. Si $n+1$ no es un número primo entonces existe alguna divisor $a\mid (n+1)$, lo $2 \le a \le n$.

Por hipótesis de inducción, sabemos que $a$ es divisible por los números primos $p$. Desde $p \mid a $ $a \mid (n+1)$ se sigue que $p \mid (n+1)$ y la prueba está completa.

Si quieres hacer esto con la debilidad de la inducción tendrá que cambiar la declaración de que quieren demostrar algo menos intuitiva.

Answer 4

A menudo es conceptualmente más fácil pensar en un argumento en términos de una fuerte inducción. Es cierto que siempre se puede refundido de la prueba en términos de la debilidad de la inducción (aunque yo no siga exactamente los comentarios que estamos haciendo en el ejemplo de la pregunta--¿qué tienes que hacer para hacer que el argumento débiles de la inducción es el cambio en la declaración que se prueba por inducción a partir de "$P(k)$ "" $P(i)$ es cierto para todos los $i\leq k$"), pero es un poco más simple para usar una fuerte inducción directamente. Yo podría hacer de su pregunta y pregunto: ¿por qué debería utilizar nunca débil de la inducción, cuando es reemplazable por una fuerte inducción? Es en gran medida una cuestión de gusto, y la versión que lleva a una más fácil comprensión de prueba para el problema en particular que usted está tratando de resolver.

Además de eso, el concepto de la fuerte inducción generaliza mejor que la debilidad de la inducción. Fuerte de inducción funciona sobre cualquier bien ordenada (o incluso, de manera más general, cualquier conjunto equipado con una bien fundada relación). De esta forma generalizada de inducción, llamada inducción transfinita, es extremadamente importante en la teoría de conjuntos y también tiene aplicaciones en muchas otras áreas de las matemáticas, y no puede ser reducida a la debilidad de la inducción de la misma manera ordinaria de la inducción puede. (Bueno, hay una especie de "débil inducción" versión de inducción transfinita dado por la división en sucesor y limitar los casos, pero es todavía bastante diferente de la ordinaria débil de inducción debido a que el límite de los casos, además de a $0$. Y esto no funciona en absoluto al realizar la inducción en general bien fundado de las relaciones.)