Ejemplos de inducción matemática

Question

¿Cuáles son los mejores ejemplos de inducción matemática disponibles en el nivel de la escuela secundaria -totalmente elemental- que hacen no implican expresiones de la forma $\bullet+\cdots\cdots\cdots+\bullet$ donde el número de términos depende de $n$ y estás haciendo la inducción en $n$ ?

Posdata tres años después: Veo que he redactado esta última parte de forma un tanto torpe. Lo dejaré ahí pero lo reformularé aquí:

--- que son no casos de inducción sobre el número de términos de una suma?

Answer 1

Yo utilizaría un método visual para explicar el concepto antes de "complicarlo" con números. Las fichas de dominó que caen parecen intuitivas y captan la esencia de la inducción.

Para visualizarlo, piense en las declaraciones como fichas de dominó, alineadas en un fila. Imagina que puedes demostrar la primera afirmación S1, y simboliza esto como el dominó S1 siendo derribado. Además, imagine que puede demostrar que cualquier afirmación Sk que sea verdadera (que caiga) obliga a la siguiente declaración Sk+1 a ser verdadera (a caer). Entonces, S1 cae y derriba a S2. A continuación, S2 cae y derriba a S3, luego S3 derriba a S4, y así y así sucesivamente. La conclusión ineludible es que todos los enunciados son derribados (se ha demostrado que son verdaderas).

(Fuente: p143 de Libro de las pruebas por Richard Hammack)

(También podría salirse por la tangente sobre abstracción en las analogías matemáticas .)

Answer 2

¿Probar afirmaciones como $f(n) \leq g(n)$ ¿se ajusta a su perfil? Por ejemplo, demostrar que $2^n \leq 2n!$ .

Answer 3

Estos me vienen a la mente de inmediato; puede que tenga más después.

1. El número de vértices de un árbol es uno más que el número de aristas.

2. Si $n>0$ exactamente la mitad de los subconjuntos de $\{1,\dots,n\}$ tienen una cardinalidad par.

3. Cualquiera de los muchos dos implica finito argumentos. Por ejemplo, si $\mathscr{C}$ es una colección de conjuntos con la propiedad de que $C_0\cap C_1\in\mathscr{C}$ siempre que $C_0,C_1\in\mathscr{C}$ entonces $\mathscr{C}$ es cerrado bajo intersecciones finitas.

4. La inducción del sello postal: dado un suministro ilimitado de $3$ y $5$ de centavos, cada cantidad entera mayor que $8$ se puede hacer. O si lo prefiere: si $A$ es un conjunto de enteros positivos tal que $3,5\in A$ y $a+b\in A$ siempre que $a,b\in A$ entonces $A$ contiene todos los enteros mayores que $8$ .

5. Todo tipo de inducciones simples basadas en definiciones recursivas de cadenas de símbolos. Por ejemplo, $aba$ es un palabra legal y si $w$ es una palabra legal, también lo son $abw,awb,wab,baw,bwa$ y $wba$ ; demostrar que cada palabra legal contiene más $a$ que $b$ 's.

Answer 4

¿Qué te parece que un grafo tenga siempre un número par de vértices de grado impar, por inducción sobre el número de aristas? Pero tal vez el argumento del recuento sea más sencillo.

En la misma línea: Euler's $F-E+V=2$ fórmula para los gráficos. Polinomios cromáticos.

Answer 5

El número de diagonales de un polígono convexo es $n(n-3)/2$ .

Prueba

Para $n=3$ El resultado es el siguiente.

Supongamos que es cierto para $n$ y mira $n+1$ . Uniendo los vértices $1$ con vértice $3$ obtenemos un polígono con $n$ lados. La hipótesis inductiva significa que tenemos $n(n-3)/2$ . diagonales, más la que acabamos de dibujar. Sólo tenemos que añadir las diagonales que faltan de $2$ a todos los demás vértices $\neq 1,3$ , lo que supone $n-2$ más diagonales. Por lo tanto, obtenemos $$\frac{n(n-3)}2+n-2+1=\frac{n(n-3)+2(n-1)}{2}=\frac{n^2-n-2}{2}=\frac{(n-2)(n+1)}2$$

y el resultado es el siguiente.