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

Un ejemplo clásico es la prueba de El lema de Sperner donde se sustituye la condición más débil de la existencia de un simplex con todos los colores mostrando que el número de tales simplex es impar.

Answer 2

Teorema (difícil): Todo grafo plano puede tener sus aristas dirigidas de forma que el indegree de cada vértice sea $\leq 3$ .

Fortalecimiento (fácil): Todo grafo plano puede tener sus aristas dirigidas de forma que el grado de cada vértice sea $\leq 3$ y el grado de cada vértice en la frontera es $\leq 2$ .

Prueba: Dejemos que $G$ sea un grafo plano y dejemos que los vértices de la frontera se denoten $x_1, x_2, x_3, \dots, x_n$ en orden cíclico. Definir el subgrafo $H < G$ borrando $x_2$ y todas las aristas incidentes. Entonces utilizamos la hipótesis de inducción para dirigir legítimamente las aristas de $H$ y ampliarlo a $G$ al tener $x_2$ tienen dos aristas entrantes (de $x_1$ y $x_3$ ) y todas las demás aristas sean salientes. El caso base es trivial, por lo que el resultado se obtiene por inducción en el orden de $G$ . QED

Curiosamente, cuando se planteó el problema original en una prueba de selección para determinar el equipo británico de la OMI, sólo una persona encontró esta elegante prueba (que creo que desconocían los encargados de plantear el problema, que en cambio tenían un meticuloso argumento con la fórmula de Euler.

Answer 3

Este es un ejemplo sencillo que encontré en Miniaturas matemáticas .

$\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} < \frac{1}{\sqrt{3n}}$

El paso de la inducción se reduce a querer $$\frac{2n+1}{2(n+1)} < \frac{\sqrt{3n}}{\sqrt{3(n+1)}}$$

lo que desgraciadamente no es cierto. Sin embargo, si la hipótesis de la inducción se refuerza ligeramente a

$\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} \le \frac{1}{\sqrt{3n+1}}$

la inducción funciona sin problemas.

Por cierto, en el libro se menciona que Pólya se refiere a este fenómeno de fortalecimiento de la hipótesis de inducción como "la paradoja del investigador", aunque no parece que la frase se haya puesto de moda.

Answer 4

Hay una exposición detallada de esta técnica de prueba en el libro de Knuth Números surrealistas . Los personajes del libro desarrollan la idea gradualmente.

En Álgebra con teoría de Galois de Emil Artin (y probablemente todos los demás libros), cualesquiera dos campos de división de f(x) sobre F son isomorfos se demuestra limpiamente en generalizando el predicado para decir que si dos campos son isomorfos entonces se extienden a campos de división isomorfos. El mismo tipo de generalización ocurre repetidamente en los argumentos de corrección de programas recursivos simples.

Esta técnica de prueba también engendra una técnica de programación: Añadir un nuevo parámetro a una función recursiva (lo que corresponde a la generalización del predicado de inducción) permite a menudo dar algoritmos más eficientes. Como ejemplo sencillo, considere la conversión de las hojas de un árbol en una lista de Deforestación: programas de transformación para eliminar árboles .

Otro ejemplo de la informática es el método de los candidatos a la reducibilidad (que se explica en Pruebas y tipos ) utilizado para demostrar la normalización fuerte para varias formas de cálculo lambda.

Answer 5

La reseña de Paul Goerss del libro "Differential algebras in topology" de David Anick contiene la siguiente observación:

"...los espacios $D_k$ se construyen y analizan de forma inductiva, con seguramente la mayor hipótesis inductiva que he visto nunca".