19 votos

Excelentes usos de la inducción y la recursividad

¿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.

35voto

Roland Puntos 315

Un clásico: Fijar un número entero positivo $n$ . Demuestre que es posible embaldosar cualquier $2^n \times 2^n$ cuadrícula con exactamente un cuadrado eliminado utilizando fichas en forma de "L" de tres cuadrados.

Sirve como magnífico ejemplo introductorio a la demostración por inducción. De hecho, la prueba casi puede representarse con dos figuras apropiadas. Sin embargo, para los que acaban de aprender inducción, se trata de un problema importante en el que la aplicación de la hipótesis inductiva dista mucho de ser obvia.

14voto

Marius K Puntos 395

El espacio de Tsirelson (1974) es un buen ejemplo de la teoría de los espacios de Banach. Su espacio es la terminación de un $c_{00}$ (todas las secuencias escalares finitamente soportadas) bajo una norma definida inductivamente. La norma base es la supranorma $\|\cdot \|_0$ .

Para $n \in \mathbb{N}$ la norma $\|x\|_{n+1}$ se define por

$ \|x\|_{n+1}= \sup\{\frac{1}{2} \sum^k_i \|E_ix\|_{n} \} $

donde el supremum se toma sobre todos los conjuntos $(E_i)_{i=1}^k$ donde $E_i$ es un intervalo finito en $\mathbb{N}$ , $\max E_i < \min E_{i+1}$ y $k \leq E_1$ (aquí $Ex$ denota la restricción de $x$ a las coordenadas de $E$ ). La norma de Tsirelson es $\|x\|_T = \sup_n \|x\|_n$ y satisface la siguiente ecuación implícita

$ \|x\|_T= \max ( \|x\|_0 , \sup \frac{1}{2} \sum^k_i \|E_ix\|_T ).$

El espacio $T$ no contiene una copia de ningún $\ell_p$ o $c_0$ . Esto resolvió un importante problema abierto en su momento (debo señalar que Tsirelson definió en realidad el dual de $T$ que también tiene la propiedad).

El método inductivo que ideó para producir este espacio condujo finalmente a la solución de numerosos problemas de la teoría de los espacios de Banach (demasiados para mencionarlos). Además, la "necesidad" de la construcción inductiva de producir espacios que no contengan ningún $\ell_p$ de $c_0$ es un problema que ha sido considerado por Gowers como un proyecto de polímata (desgraciadamente no se ha avanzado mucho en este sentido): http://gowers.wordpress.com/2009/02/17/must-an-explicitly-defined-banach-space-contain-c_0-or-ell_p/

Visite el sitio web de Boris Tsirelson para más información sobre su espacio: http://www.math.tau.ac.il/~tsirel/Investigación/myspace/main.html

13voto

John Mac Puntos 1095

En $n$ -nivel Torre de Hanoi puede resolverse en $2^n - 1$ se mueve.

La inducción no sólo lo demuestra, sino que te muestra la solución.

8voto

Chris Bunch Puntos 639

El siguiente rompecabezas famoso es un gran ejemplo:

http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/

8voto

cjk Puntos 363

1)Demostración de la fórmula de Euler, V-E+F=2, con inducción en F (número de caras).

2)Prueba por inducción hacia atrás de la desigualdad generalizada AM-GM.

3)Demostración del teorema de Heine-Borel mediante Transfinito Inducción topológica.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X