Excelentes usos de la inducción y la recursividad

Question

¿Puede poner un ejemplo de gran ¿prueba por inducción o construcción por recursión?

Dado que usted ya tiene su propia idea de lo que significa "genial", aquí también puede entenderse que la técnica elegida :

• es vital para el argumento;
• arroja nueva luz sobre el propio resultado;
• ofrece una forma elegante de cumplir la tarea;
• transmite una visión poderosa y sencilla de un asunto intrincado;
• es la única forma natural de abordar el problema.

Aquí la inducción y la recursividad se entienden en el sentido más amplio de las palabras, pueden abarcar desde la inducción sobre los números naturales hasta la recursividad bien fundada, pasando por la inducción transfinita, etc...

Se valorarán especialmente los ejemplos de nivel elemental, pero también los de nivel no elemental.

Answer 1

Teorema de Goodstein aún no se ha mencionado. Un teorema aritmético de apariencia sencilla con una demostración sorpresa mediante inducción transfinita. Además (la principal característica interesante del teorema), NO hay demostración a partir de aritmética Peano ordinaria de primer orden. En realidad es equivalente al formalizado $\Sigma^0_1$ -sonoridad (aka 1-consistencia) de PA.

Answer 2

Inducción simultánea utilizada en la teoría combinatoria de grupos, por ejemplo en la demostración del teorema de Adyan-Novikov que proporciona el contraejemplo al problema general de Burnside:

En respuesta a una de mis preguntas sobre esta prueba, Mark Sapir proporcionó algunas buenas referencias al respecto:

¿Una sinopsis de la solución de Adyan al problema general de Burnside?

Sin duda, la técnica de inducción simultánea es una idea importante para construir estos grupos monstruosos.

Answer 3

El problema de "Hércules y la Hidra", en "L. Kirby and J. Paris. Resultados de independencia accesibles para la aritmética peano. Sociedad Matemática de Londres , 4:285 293, 1982.".

Utilizando la inducción transfinita, es posible demostrar que Hércules siempre matará a la hidra (con un número finito de golpes) independientemente de la estrategia elegida para cortar las cabezas de la hidra. Además, este hecho no es demostrable dentro de la aritmética de Peano.

Answer 4

Un problema con el que disfruté en mi curso de algoritmos de licenciatura es el siguiente:

Supongamos que tienes una máquina de computación con la siguiente arquitectura. Existen $k$ pilas (para algunos $k$ ), la entrada se puede introducir en la primera pila, la salida se extrae de la última y las operaciones intermedias se extraen de una pila y se introducen en la siguiente en una línea. La parte superior de la pila también puede inspeccionarse y compararse. Dada una permutación de $\{1,\ldots,n\}$ en orden como entrada, cuántas pilas $k$ ¿necesita ordenar la permutación? Describe un algoritmo que alcance este límite.

Se puede demostrar el límite ( $\log_2 n$ ) por inducción, y luego simplemente afirmar que esto da un algoritmo recursivo natural. La misma técnica fue útil para un par de problemas similares.

Creo que esta es una forma elegante de cumplir la tarea (demostrar un límite y dar un algoritmo que lo consiga) en una buena clase de casos.

El problema es original de Knuth Vol. 1, y la ordenación por pila se explica con más detalle en esta encuesta .

Answer 5

Sea $P(p)$ = "no hay $q$ tal que $(p/q)^2=2$ ". Un simple argumento de inducción muestra que P se cumple para todos los naturales $p$ y, por tanto, que $\sqrt 2$ es irracional. Todos los argumentos de descendencia son básicamente inducción.