Ejemplos clásicos de inducción matemática

Question

¿Cuáles son algunas pruebas interesantes, estándar, clásicas o sorprendentes utilizando inducción?

Esto es lo que tengo hasta ahora:

• Hay algunas sumas muy estándar, por ejemplo, $\sum_{k=1}^n k^2$, $\sum_{k=1}^n (2k-1)$, y así sucesivamente.
• Propiedades de Fibonacci (hay varias clásicas).
• El rompecabezas de la Torre de Hanoi se puede resolver en $2^n-1$ pasos.
• Un cuadrado $2^n \times 2^n$ con un cuadrado faltante se puede cubrir con $L$-tríominos.
• La fórmula de Cayley para bosques etiquetados.
• Cada cuadrado se puede subdividir en cualquier número $n \geq 6$ de subsquares.
• El problema de la galería de arte.
• Número de regiones determinadas por $n$ líneas en posición general.
• La fórmula de Euler $V-E+R=2$.
• Los grafos planos son 5-colorables.
• Propiedades sobre coeficientes binomiales (no cuento estos como clásicos, ya que las pruebas son muy mundanas y no realmente divertidas - en mi humilde opinión, tales identidades deberían ser probadas por un argumento biyectivo / interpretación combinatoria).

En otras palabras, ¿qué esperarías ver en un libro titulado "Inducción en Matemáticas", dirigido a estudiantes de primer año/universitarios?

Realmente me gusta el problema de los tilings con $L$-tríominos: es fácil de plantear, tiene una prueba ingeniosa que requiere cierta creatividad.

Se apreciarían ejemplos interesantes de cálculo y probabilidad.

Answer 1

Si deseas dividir la barra de chocolate a continuación en sus $28$ piezas individuales, ¿cuál es el número mínimo de quiebres que se necesitan para hacerlo? Solo puedes dividir un trozo de chocolate en dos piezas a la vez.

La respuesta es que, por supuesto, se necesitan exactamente $27$ quiebres, sin importar cómo lo hagas. Esto suele sorprender a la gente, ya que muchos piensan que tal vez dividir el trozo en 'trozos iguales' o romper cualquier trozo a lo largo de la línea del quiebre más largo terminaría haciendo las cosas más rápido. Sin embargo, una rápida y simple demostración por inducción (fuerte) muestra que tienen que ser $n-1$ quiebres para $n$ piezas.

También, puedes continuar este problema con: Toma la misma barra de chocolate de arriba, y una vez más quieres dividirla en sus $28$ unidades individuales. Esta vez, sin embargo, puedes obtener puntos cada vez que realizas un quiebre: Si rompes un trozo de chocolate de tamaño $n$ en dos piezas de tamaño $k$ y $n-k$, entonces recibes $k \cdot (n-k)$ puntos. Ahora: ¿cuál es el número máximo de puntos que puedes obtener?

Y de nuevo, puedes demostrar por inducción fuerte que sin importar cómo dividas la barra, tu puntaje total al final será $\frac{n(n-1)}{2}$. Aquí hay una demostración con imagen, sabiendo que $\frac{n(n-1)}{2}$ es la suma de todos los números desde $1$ hasta $n-1$ (es decir, el número triangular $T_{n-1}$):

Esta imagen muestra que $T_{n-1}=k(n-k)+T_{k-1}+T_{n-k-1}$, entonces usando la hipótesis inductiva de que el puntaje que obtienes al romper un trozo de chocolate de tamaño menor a $n$ siempre te da un puntaje de $T_{k-1}$, sin importar cómo lo rompas, obtenemos que el puntaje de romper el trozo con $n$ piezas te da $k(n-k)+T_{k-1}+T_{n-k-1}=T_{n-1}$ puntos, sin importar dónde coloques el próximo quiebre.

Answer 2

Un libro "dirigido a los principiantes" no debería perder el ejemplo de un simple error posible en un razonamiento inductivo como Todos los caballos son del mismo color.

Answer 3

Todo entero mayor que $1$ es o un número primo o un producto de números primos. (Inducción fuerte)

Answer 4

Teorema del recorrido de Euler (también conocido como el "Teorema de Euler" pero el Teorema del recorrido de Euler incluye tanto la existencia del Recorrido de Euler como del Circuito de Euler). Un grafo conectado tiene un circuito de Euler si y solo si no tiene ningún vértice de grado impar. Se puede demostrar con inducción fuerte como se explica aquí: http://mathonline.wikidot.com/euler-s-theorem

Answer 5

Aquí hay algunos rompecabezas lógicos conocidos, para los cuales utilizas la inducción para demostrar la corrección de la respuesta:

Botín de pirata

Islas de ojos azules