¿Por qué la inducción matemática no funciona al revés o con incrementos distintos de 1?

Question

Desde mi punto de vista, si una afirmación es verdadera para $n = 1,$ y se asume que una afirmación es verdadera para un número entero arbitrario $k$ y demostrar que la afirmación también es cierta para $k + 1,$ entonces demuestras que la afirmación es verdadera para todos $n \ge 1$ . Tiene sentido.

Sin embargo, ¿por qué no puedo hacerlo al revés? Si muestro que la afirmación es verdadera para $k - 1,$ ¿no estoy demostrando que si la afirmación es verdadera para $n = 1,$ es igualmente cierto para $n = 0, n = -1, n = -2, \ldots$

Además, ¿por qué no puedo demostrar que la afirmación es cierta para $k + 0.1,$ y demostrar que la afirmación es verdadera para $n = 1.1, 1.2, 1.3, \ldots?$ Ambos escenarios, en mi mente, parecen seguir la misma lógica que la definición "adecuada" de la inducción matemática, pero aparentemente no son válidos. ¿Puede alguien explicar por qué?

Gracias.

Edición: El consenso parece ser que sí, aunque sea anormal, la inducción, como he dicho arriba, es lógicamente sólida. Lo que plantea la pregunta: ¿por qué mi profesor de matemáticas ha dicho que esto es incorrecto? ¿Es, como sospecho, que no quiere que me desvíe de la definición correcta de $k + 1$ inducción y posiblemente confundirme (o perder puntos en el examen), o hay algo más que hace que lo anterior sea fundamentalmente defectuoso?

Gracias.

Answer 1

Sí funciona de las dos maneras que has sugerido. Normalmente los problemas de inducción se plantean de forma que se quiere demostrar $P(n)$ para todos los números naturales $n$ . Entonces se empieza con $P(1)$ y pasar de $n$ a $n+1$ . Sin embargo, si quisieras demostrarlo para números enteros negativos, empezarías con $P(-1)$ y pasar de $n$ a $n-1$ . Por supuesto, puede cambiar la variable $m:=-n$ y reducir el segundo caso al primero. Lo mismo ocurre con tu otro ejemplo con $m:=10(n-1)$ . Dado que la inducción "hacia atrás" y la "fraccionada" se reducen a la inducción estándar, están igualmente justificadas.

Answer 2

Voy a ser valiente y estar en desacuerdo con la mayoría de las otras respuestas. (Excepción: Estoy de acuerdo con la respuesta de Dan Piponi, a la que he dado un voto más alto, pero creo que esa respuesta entierra el tema).

Te han dado un teorema en clase, de este estilo:

Dejemos que $P(n)$ ser una declaración sobre $n$ con estas propiedades:

1. $P(1)$ es cierto.
2. Para todos $k \in \mathbb{N}$ , si $P(k)$ es verdadero, entonces $P(k+1)$ es cierto.

Entonces $P(n)$ es cierto para todos los $n \in \mathbb{N}$ .

y tu profesor quiere que escribas pruebas utilizando ese teorema.

Usando su intuición matemática, ha adivinado correctamente que hay muchos otros teoremas similares, como un teorema para cubrir "todos los enteros $m \le 1$ " comenzando con $1$ y contando hacia atrás, y un teorema para cubrir "todos los números de la forma $1+\frac{p}{10}, p \ge 0$ ". Pero esos teoremas no son "dados"; no aparecen en tu libro de texto y tu profesor no te los ha enseñado. Cuando te piden que escribas una demostración para la clase, es un requisito tácito que tu demostración dependa sólo de un cierto conjunto de resultados preexistentes que está bien que utilices: los axiomas y teoremas que te han dado en clase, más (probablemente) el álgebra mecánica y la aritmética. Sin ese requisito tácito, podrías "demostrar" todo simplemente afirmando que es un enunciado correcto y, por tanto, demostrado. Así que creo que tu profesor tiene razón al esperar que utilices la formulación canónica de la inducción que te han dado en clase, en lugar de otros teoremas similares.

Dicho esto, sus teoremas modificados pueden demostrarse de forma bastante sencilla como corolarios de la inducción matemática habitual. La respuesta de Dan Piponi muestra cómo hacerlo para uno de tus teoremas. Así que puedes usar tus teoremas modificados, pero sólo como un paso intermedio: primero demuestras el teorema modificado, y luego lo usas para demostrar lo que realmente se te pide que demuestres. Pero esto es probablemente un trabajo innecesario; también podrías combinar los dos pasos y escribir tu demostración directamente en términos del teorema que te han dado.

Answer 3

Considere el primer ejemplo de la cuenta atrás:

Supongamos que la propiedad $Q(n)$ se mantiene para $n=1$ . Supongamos también que $Q(n)$ implica $Q(n-1)$ .

Definir una nueva propiedad $P$ por $P(n)$ si y sólo si $Q(2-n)$ .

Suponemos que $Q(1)$ para que sepamos $P(1)$ . Supongamos que $P(n)$ . Esto implica $Q(2-n)$ . Deducimos $Q(2-n-1)$ que es $Q(2-(n+1))$ . Y eso implica $P(n+1)$ .

Así que podemos usar la inducción para encontrar que $P(n)$ es válida para todos los $n\ge 1$ .

Y, por lo tanto, Q(n) se mantiene para todos los $n\le 1$ .

Así que la cuenta atrás funciona bien. Pero si aún no has demostrado que funciona necesitas demostrarlo al menos una vez desde el argumento de inducción habitual.

Un razonamiento similar muestra que tu segundo ejemplo también funciona bien.

Answer 4

Incluso en los números naturales, usted puede argumentar al revés.

Propuesta. Supongamos que $A \subseteq \mathbb{N}$ tiene la propiedad de que cada $a \in A$ o bien es igual a $0$ o bien satisface $a-1 \in A$ . Entonces $A$ está cerrado hacia abajo. (Lo que significa que para todos los $a \in A$ y $b \in \mathbb{N},$ si $b<a$ entonces $b \in A$ .)

Sin embargo, no creo que sea muy útil. Afortunadamente, una variante más útil de la inducción "hacia atrás" se aplica a los números enteros:

Propuesta. Supongamos que $A \subseteq \mathbb{Z}$ tiene la propiedad de que cada $a \in A$ satisface $a-1 \in A$ . Entonces $A$ está cerrado hacia abajo. (Lo que significa que para todos los $a \in A$ y $b \in \mathbb{Z},$ si $b<a$ entonces $b \in A$ .)

Por cierto, una buena forma de ver la inducción es a través de las álgebras libres.

Reclamación. Dejemos que $T$ denotan una teoría ecuacional, $X$ denotan un conjunto, y escribimos $Z$ para el $T$ -generada libremente por $X$ . Supongamos también que $A$ denota un subconjunto de $Z.$ Entonces, si

1. $X \subseteq A$ y
2. $A$ es un $T$ -subálgebra (de $Z$ )

entonces $A$ cubre la totalidad de $Z$ .

Por ejemplo, podemos pensar en $\mathbb{Z}$ como el objeto generado libremente por $X=\{0\}$ con respecto a la teoría ecuacional con dos operaciones unarias $S$ y $P$ , con sujeción a los axiomas $S(P(n))=n$ y $P(S(n))=n$ . Se deduce (por la afirmación anterior) que si $A$ es un subconjunto de $\mathbb{Z}$ que se cierra bajo $S$ y $P$ e incluye $0$ entonces $A$ cubre la totalidad de $\mathbb{Z}$ .

Answer 5

También puede tener pasos mayores que uno, por ejemplo, para demostrar que todos los números de al menos 12 pueden representarse sumando 3s y 7s: \begin{align} 12 &= 3 + 3 + 3 + 3 \\ 13 &= 7 + 3 + 3 \\ 14 &= 7 + 7 \end{align} Ahora puedes construir $12 + 3 k$ para cualquier $k \ge 0$ y algo similar para los otros dos. Como se intercalan, cubren todos los números prometidos.