¿Cómo funciona la inducción hacia atrás para demostrar una propiedad para todos los naturales?

Question

Estaba leyendo una entrada de blog aquí: http://mzargar.wordpress.com/2009/07/19/cauchys-method-of-induction/ ( La máquina del retroceso )

Una cosa que me desconcertó fue que después de las primeras cuatro grandes ecuaciones mostradas, está la afirmación "es suficiente demostrar que si el teorema se cumple para $n=m+1$ , entonces se cumple para $n=m$ ."

¿Cómo es válido este tipo de inducción? He buscado cosas como la inducción hacia atrás, la inducción inversa y la inducción de Cauchy, pero no he podido encontrar una justificación de cómo es válida.

Con la habitual inducción hacia adelante de verificar un caso base y demostrar $P(n)\implies P(n+1)$ es fácil entender intuitivamente cómo la inducción mostrará que una propiedad es válida para todos los números naturales (o al menos a partir del caso base). Pero con esta inducción inversa, me parece que si se demuestra $P(m+1)\implies P(m)$ Entonces, si pudieras verificar un caso específico como $P(15)$ entonces sólo se sabría que es cierto para los números hasta $15$ . ¿Cómo demuestra realmente la propiedad para todos los naturales?

Answer 1

Como bien señala el OP, $P(m+1) \Rightarrow P(m)$ por sí sola no implica que la propiedad se mantenga para todos los números naturales. El método propuesto necesita dos condiciones:

• La propiedad se mantiene para infinitos números naturales; es decir, se mantiene para una subsecuencia infinita $n_1 < n_2 < \cdots < n_k < \cdots$ . Esto es como el "paso base" de la prueba.

• $P(m+1)$ implica $P(m)$ . Este es el "paso de inducción".

Un ejemplo de libro de texto de este método es la prueba de Cauchy de la desigualdad AM-GM. La respuesta de Martin enlaza con una prueba de "la convexidad del punto medio implica convexidad" que utiliza una idea similar.

Prueba de corrección. La intuición detrás de esto es que el paso de la base identifica infinitos números para los que la propiedad se mantiene. Pero estos números pueden contener huecos; entonces trabajamos para llenar estos huecos en el paso de inducción.

Hagamos de esto una prueba formal. Supongamos que la propiedad $P$ no se mantiene para al menos un valor de $n$ , digamos que $N$ . Entonces, reescribiendo la segunda hipótesis de forma contrapuesta como $\lnot P(m) \Rightarrow \lnot P(m+1)$ y aplicando la inducción matemática estándar a la hipótesis $\lnot P$ concluimos que $\lnot P(n)$ es válida para todos los $n \geqslant N$ En otras palabras, la propiedad $P$ no se mantiene finalmente. Pero esto contradice la primera suposición. $\quad\diamond$

Termino con una observación metodológica. Obsérvese que lo que he denominado el paso básico requiere, de hecho, que demostremos la proposición $Q(k) := P(n_k)$ para infinitamente muchos $k$ . Esto recuerda a la inducción estándar, y no es de extrañar que a menudo recurramos a ella en este paso. Por ejemplo, en la prueba de AM-GM, es fácil demostrar que la desigualdad de AM-GM se cumple para $2K$ números asumiendo que siempre se mantiene para $K$ números; ajuste $K = 2^k$ da una prueba de inducción estándar de que $Q(k) := P(2^k)$ es cierto para todos los $k$ .

Answer 2

La inducción de Cauchy consta de las siguientes partes.

Queremos demostrar que $P(n)$ es válida para cualquier $n=1,2,3,\ldots$ . Para ello mostramos:

1. $P(1)$ es cierto;
2. $P(n)$ implica $P(2n)$ ;
3. $P(m+1)$ implica $P(m)$ .

Si todo de las condiciones anteriores son ciertas, entonces $P(n)$ se mantiene para todos los enteros.

---

La intuición detrás de esto: Por pasos del tipo $n\to 2n$ et $m+1\to m$ podemos obtener de $1$ a cualquier número entero. Por ejemplo, si queremos llegar al número $5$ podemos hacerlo así:
$1\to2\to4\to8\to7\to6\to5$ .
Una posibilidad diferente:
$1\to2\to4\to3\to6\to5$ .

---

Prueba formal: Supongamos que las condiciones anteriores son ciertas. Demostraremos por inducción fuerte que $P(n)$ es verdadera para cada $n$ .

$1^\circ$ Para $n=1$ tenemos validez de $P(1)$ .

$2^\circ$ Supongamos que $n\ge 2$ et $P(k)$ es verdadera para cada $k$ tal que $1\le k<n$ .

Si $n$ es par, podemos utilizar 2: Como $k=n/2<n$ sabemos que $P(k)$ es verdadera, y por lo tanto $P(2k)=P(n)$ es cierto.

Si $n$ es impar, podemos utilizar 3: Ya que $k=(n+1)/2<n$ sabemos que $P(k)$ es verdadera. Esto implica que $P(2k)=P(n+1)$ es cierto. Ahora usando 3 obtenemos que $P(n)$ también es cierto.

---

Enlaces útiles:

• Inducción de Cauchy en AoPS
• Prueba de AM-GM utilizando este tipo de inducción en Wikipedia ( revisión actual ). A esta técnica la denominan inducción hacia delante y hacia atrás.
• Una sección de la obra de Pete L. Clark notas sobre la inducción ( La máquina del retroceso ) se dedica a este tipo de inducción. Lo llama inducción ascendente-descendente.

La desigualdad AM-GM es, de hecho, la aplicación más frecuente utilizada para ilustrar la inducción de Cauchy. Puedes encontrar algunas pruebas utilizando la inducción de Cauchy y algunos enlaces útiles, por ejemplo, en estas respuestas:

• Desigualdad AM-GM
• Desigualdad AM-GM
• convexidad del punto medio y convexidad racional

Answer 3

Sugerencia $\ $ Esto puede verse como una especie de intervalo (o segmento ) de inducción.

Lema $\rm\ S\subset \mathbb N\:$ satisface $\rm\:n+1\in S\:\!\Rightarrow n \in S\:$ si $\rm\:S\:$ es un segmento inicial de $\:\mathbb N$

Prueba $ $ (pista) $ $ Si $\rm\:S\ne \mathbb N\:$ entonces $\rm\:S = [0,m)\:$ para los menos $\rm\:m\not\in S,\:$ ya que por inducción, la no pertenencia asciende desde $\rm\:m\:$ por $\rm\:n\not\in S\:\Rightarrow\:n+1\not\in S.\:$

Corolario $ $ Si, además, $\rm\:S\:$ no tiene límites, entonces $\rm\:S = \mathbb N$

En su caso $\rm\: S\ne \{\ \}\:$ es ilimitado a través de la hipótesis $\rm\:n\in S\:\Rightarrow\:2\:\!n\in S.$

Answer 4

Parece que te confundes con el método del descenso infinito que se utiliza para demostrar que algo es FALSO : Si $P(0)$ es falso y si $P(n)$ implica que existe un $m < n$ tal que $P(m)$ entonces $P(n)$ es falso para todos los $n$ . Esto corresponde a demostrar la anteposición del principio de recurrencia estándar. (La anteposición de una implicación $A\Rightarrow B$ es $\text{not} B \Rightarrow \text{not} A$ .)

Answer 5

En las respuestas encontrarás la teoría general de la idea. Pero para entender cómo funciona una buena idea es examinar la siguiente prueba de una "variante débil" de esta teoría de la inducción.

Lema 1: Sea $S$ sea un subconjunto de los números naturales $\Bbb N$ que satisfaga, para cada $n \ge 0$

$\tag 1 n \in S \text{ implies } n + 1 \in S$ $\tag 2 n+ 1 \in S \text{ implies } n \in S$

Entonces $S = \Bbb N$ o $S = \emptyset$ . Prueba
Si el conjunto no está vacío, entonces existe un $\hat k \in S$ . Utilizando $\text{(1)}$ y aplicando la inducción débil, vemos que si $k \ge \hat k$ entonces $k \in S$ . A continuación, utilice el lema del "segmento inicial" de Bill Dubuque para demostrar que $k \le \hat k$ implica $k \in S$ . $\quad \blacksquare$