Reforzar la hipótesis de la inducción

Question

Supongamos que se trata de probar el resultado $X$ por inducción y no están llegando a ninguna parte rápidamente. Un buen truco es intentar demostrar un resultado más fuerte $X'$ (que realmente no te importa) por inducción. Esto tiene una posibilidad de éxito porque tienes más con qué trabajar en el paso de inducción. Mi ejemplo favorito de esto es la hermosa prueba de Thomassen de que todo grafo planar es 5-elegible. La prueba es bastante sencilla una vez que se sabe lo que hay que demostrar. Aquí está la forma reforzada (que es un buen ejercicio para demostrar por inducción),

Teorema. Dejemos que $G$ sea un grafo plano con al menos 3 vértices tal que cada cara de $G$ está delimitada por un triángulo (excepto posiblemente la cara exterior). Sea la cara exterior de $G$ estar delimitado por un ciclo $C=v_1 \dots v_kv_1$ . Supongamos que $v_1$ se ha coloreado 1 y que $v_2$ se ha coloreado 2. Supongamos además que para cualquier otro vértice de $C$ se ha especificado una lista de al menos 3 colores, y para cada vértice de $G - C$ se ha especificado una lista de al menos 5 colores. Entonces, la coloración de $v_1$ y $v_2$ puede extenderse a una coloración de $G$ con las listas especificadas.

Pregunta 1. ¿Cuáles son otros buenos ejemplos de este fenómeno?

Pregunta 2. ¿En qué condiciones es probable que funcione la estrategia de reforzar la hipótesis de inducción?

Answer 1

Este es un consejo que me costó aprender:

No es necesario saber lo que se está demostrando cuando se empieza a escribir una prueba por inducción.

El siguiente método no es necesario para los problemas fáciles, pero en varias ocasiones me ha servido para obtener un lema que no se podía obtener de ninguna otra manera. Después de haber trabajado en el problema durante una semana más o menos y tener una buena sensación de él, escribe todas las condiciones que parecen ser relevantes. Escribe todas las implicaciones que puedas demostrar de la forma "Si las condiciones del conjunto $S$ para algunos valores de los parámetros, entonces las condiciones del conjunto $T$ se mantienen para otros valores". Descartar cualquier en el que se establezca $S$ puede ser encogido, o $T$ ampliado. Ahora, dibuja un gráfico con flechas entre los conjuntos. Busca un bucle en este gráfico, un camino desde tu hipótesis hasta el bucle, y un camino desde el bucle hasta tu conclusión. Si encuentras uno, entonces tienes una prueba potencial por inducción, suponiendo que tus parámetros "disminuyen" a medida que recorres el bucle.

Esta es la otra parte del truco. Cuando inicie este procedimiento, no es necesario decidir qué orden va a utilizar en el conjunto de parámetros. Espera a encontrar el bucle. Entonces el bucle te da una recursión específica sobre tu conjunto de parámetros, y puedes intentar encontrar un orden bueno con respecto al cual esta recursión sea decreciente.

Había pensado en escribir una entrada en el blog sobre esto, pero todos los ejemplos que conozco son muy técnicos.

Answer 2

Un ejemplo muy sencillo:

$$1+ \frac{1}{4} + \frac{1}{9} + \cdots+ \frac{1}{n^2} < 2$$

no se puede demostrar por inducción por razones obvias, pero

$$1+ \frac{1}{4} + \frac{1}{9} + \cdots+ \frac{1}{n^2} \leq 2-\frac{1}{n}$$

es un problema de inducción fácil.

[Editar]: Se me olvidó añadir esto, aunque el ejemplo es muy sencillo, me gusta el hecho de que es fácil de entender (antes de resolver el problema) por qué la inducción no puede funcionar en el primer ejemplo y por qué podría funcionar en el caso más fuerte.

Answer 3

Un ejemplo muy conocido es la estimación $\log(n)<1+\frac{1}{2}+\cdots+\frac{1}{n}$ para la serie armónica. Es más fácil mostrar $\log(n+1)$ como límite inferior, para un paso inductivo desde $n-1$ a $n$ basta con demostrar que $\log(n+1)-\log(n)<\frac{1}{n}$ que es $\left(1+\frac{1}{n}\right)^n< e$ cuando se reordena.

Answer 4

He aquí un pequeño ejemplo del libro Matemáticas concretas :

p. 78: Deja que $K_0=1$ y $K_{n+1}=1+\min(2 K_{\lfloor n/2 \rfloor}, 3 K_{\lfloor n/3 \rfloor})$ para $n\ge 0$ . ("Uno de los autores de este libro ha decidido modestamente llamarlos los números de Knuth").

p. 97, ejercicio 3.25: Demuestra o refuta que los números de Knuth satisfacen $K_n \ge n$ para $n\ge 0$ .

La inducción falla cuando se trata de demostrar $K_n \ge n$ directamente (como se explica en el texto de la p. 79), pero funciona fácilmente para la afirmación más fuerte $K_n > n$ .

Answer 5

El ejemplo más sencillo que conozco de este fenómeno es la demostración de la conmutatividad de la suma (en $\mathbb{N}$ ). Es un pequeño y divertido ejercicio para tratar de probarlo sin lemas . Es decir, intenta encontrar un argumento inductivo que no requiera una inducción anidada o utilice un hecho auxiliar como la asociatividad de la suma.

Desde una perspectiva teórica de la prueba, es posible mostrar que la necesidad de reforzar las hipótesis de inducción es una propiedad inherente a la regla de inducción (finitaria). Los cálculos secuenciales para la lógica de primer orden satisfacen la propiedad denominada propiedad de la subfórmula que dice que todo teorema de FOL tiene una demostración que sólo implica subfórmulas del teorema a demostrar (contando $A[t/x]$ como una subfórmula de $\forall x.\;A$ ). Sin embargo, la propiedad de la subfórmula falla para la regla de inducción. En términos del cálculo secuencial, se puede dar una regla de la izquierda para que se parece a esto:

$$\frac{\Gamma \vdash B(0) \qquad \Gamma, B(j) \vdash B(s\;j) \qquad \Gamma, B(i) \vdash C }{\mathrm{nat}(i), \Gamma \vdash C}$$

Leyendo la secuencia de abajo hacia arriba, observe que la fórmula $B$ "sale de la nada" -- no es una subfórmula de $C$ o cualquiera de las hipótesis existentes $\Gamma$ . ¡Sólo tienes que inventarlo para resolver tu problema! Por eso los demostradores de teoremas informatizados son inútiles para las pruebas inductivas: no tenemos una buena heurística para elaborar hipótesis de inducción.