Ejemplos ilustrativos de un fenómeno de la lógica de la inducción matemática

Question

Se dice (y yo mismo lo he dicho) que en algunos casos la forma más fácil de demostrar un enunciado por inducción matemática es demostrar un enunciado más fuerte por inducción matemática, porque entonces uno tiene una hipótesis de inducción más fuerte para usar.

Pero entonces me pregunto: si un estudiante brillante me pidiera algunos ejemplos típicos de ese fenómeno, ¿qué le diría?

El único ejemplo que me vino a la mente inmediatamente cuando pensé en esta pregunta es teorema de os: Una frase de primer orden $\varphi$ es cierto en un ultraproducto $\left(\prod_{i\in I} A_i\right)/F$ , donde $F$ es un ultrafiltro en el conjunto de índices $I$ si y sólo si el conjunto $\{i\in I : \varphi\text{ is true in}A_i\}$ es miembro de $F$ . La afirmación más fuerte habla de fórmulas de primer orden (que pueden contener variables libres) y no de oraciones de primer orden (que no tienen variables libres). La prueba es por inducción sobre la formación de fórmulas de primer orden, y funciona ya que la clase de fórmulas de primer orden es cerrada bajo ciertas operaciones y la clase de oraciones de primer orden no lo es.

No es un gran ejemplo para la situación que imaginé.

Buscando un poco en m.s.e., encuentro la respuesta de Steven Stadnicki a esta pregunta y mi respuesta a esta pregunta y quizás la respuesta de Martin Brandenburg a esta pregunta .

No es una gran lista de ejemplos con fines ilustrativos a nivel elemental (aunque la respuesta de Steven Stadnick encajaría en dicha lista).

• Si el propósito es ilustrar este fenómeno, ¿qué ejemplos deben utilizarse, tanto en los niveles más elementales como en los más avanzados?
• ¿Existe un punto de vista lógico sobre este fenómeno? ¿Podría haber, por ejemplo, algún mapeo idempotente $T$ de la clase de afirmaciones-que-son-versiones-más-débiles-de-cosas-probables-por-inducción a la clase de cosas-probables-por-inducción, donde $T\varphi$ es en cada caso una generalización de $\varphi$ ?

Answer 1

Consideremos la fracción continua simple $\langle a_0;a_1,a_2,\dots\rangle$ donde todos los $a_i$ son números enteros, y todos positivos excepto posiblemente $a_0$ .

Definir las secuencias $p_i$ , $q_i$ por

$p_{-1}=0$ , $p_0=a_0$ y $p_k=a_kp_{k-1}+p_{k-2}$ y

$q_{-1}=0$ , $q_0=1$ y $q_k=a_kq_{k-1}+q_{k-2}$ .

Queremos demostrar que $\langle a_0;a_1,\dots,a_k\rangle=\frac{p_k}{q_k}$ .

La forma estándar de demostrar el resultado por inducción es demostrar el resultado más fuerte de que para cualquier positivo $x$ , $$\langle a_0;a_1,\dots,a_{k-1},x\rangle=\frac{xp_{k-1}+p_{k-2}}{xq_{k-1}+q_{k-2}}.$$

Como pequeño ejemplo adicional, un pregunta reciente pidió una prueba de que el denominador de $\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}}$ puede ser racionalizado. Una prueba de inducción utilizó la hipótesis de inducción más fuerte que $\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}+t}$ puede ser racionalizado, donde $t$ es un parámetro libre.

Sin embargo, para los argumentos de inducción temprana, creo que las desigualdades son bastante persuasivas, ya que está claro que, por ejemplo, saber que $1+\frac{1}{2^2}+\frac{1}{n^2}\lt 2$ no puede implicar por sí mismo que $1+\frac{1}{2^2}+\frac{1}{n^2}+\frac{1}{(n+1)^2}\lt 2$

Answer 2

Ejemplo:

Puede probar

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

reforzando a

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

y utilizando la inducción simple; este es el ejemplo más sencillo que conozco (se puede hacer la desigualdad aún más corta utilizando el doble factorial notación). De hecho hace tiempo hubo un post aquí sobre ello, pero no lo he encontrado.

Espero que esto ayude ;-)

Editar:

Acabo de ver un ejemplo aún más sencillo en esta pregunta Es decir,

Demostrar que $0 \leq a_n < 1$ para todos $n \in \mathbb{N}$ donde $a_0 = 0$ y $ a_n = a_{n-1}^2 + \frac{1}{4} $ para $n > 0$ .

que se puede resolver fácilmente demostrando $0 \leq a_n < \frac{1}{2}$ (en el post original @DanielFischer fue el primero en dar esta pista).

Answer 3

Afirmo que se puede demostrar por inducción que $\sum_{n=1}^{\infty} \frac{1}{n^2}$ converge: o, si quieres una afirmación que no utiliza nada de la teoría de series infinitas, que hay $A \in \mathbb{R}$ tal que $\sum_{k=1}^n \frac{1}{k^2} \leq A$ para todos $n \in \mathbb{Z}^+$ .

¿Tiene problemas para mostrarlo por inducción? Te lo pondré más difícil pidiéndote que demuestres que puedes tomar $A = 2$ .

¿Tienes al menos los mismos problemas que antes? Lo haré mucho más difícil.

Demuestre que para todo $n \in \mathbb{Z}^+$ , $\sum_{k=1}^n \frac{1}{k^2} \leq 2- \frac{1}{n}$ .

Pero, de hecho, la última afirmación es muy sencilla de demostrar por inducción (véase, por ejemplo, la Proposición II.2.7 aquí para los detalles, pero cualquier lector que esté medianamente familiarizado con las pruebas de inducción no tendrá problemas para proporcionarlas por sí mismo).

La última desigualdad es uno de mis ejemplos habituales cuando enseño la inducción matemática. Creo que es un buen ejemplo del tipo de fenómeno por el que preguntas. Por desgracia, también es un buen ejemplo del tipo de "teorema encontrado" que se pide a los estudiantes que demuestren utilizando la inducción. En otras palabras, supongamos que realmente intentamos resolver la primera pregunta por inducción. ¿Cómo sabríamos o averiguaríamos que hay que reforzar la desigualdad de esta manera concreta? (Ejemplos aún más estándar de "teoremas encontrados" son las omnipresentes identidades de suma de potencias, por ejemplo $\sum_{k=1}^n k^3 = \left( \frac{n(n+1)}{2}\right)^2$ .)

Answer 4

Siempre he pensado en esta cuestión utilizando el siguiente ejemplo lógico (la inducción es sobre la longitud de la fórmula proposicional):

• Toda fórmula proposicional construida con sólo $\neg, \land, \lor$ es equivalente a una fórmula (sólo con el uso de $\neg, \land, \lor$ ) donde $\neg$ sólo afecta a las variables proposicionales.

Una prueba directa de la afirmación anterior utilizando la inducción no parece funcionar. Por otro lado, una prueba (utilizando la inducción) de la siguiente afirmación más fuerte es casi trivial:

• Para cada fórmula proposicional $\varphi$ construido usando sólo $\neg, \land, \lor$ sostiene que..: 1) $\varphi$ es equivalente a una fórmula (sólo con el uso de $\neg, \land, \lor$ ) donde $\neg$ sólo afecta a las variables proposicionales, y 2) $\neg \varphi$ es equivalente a una fórmula (sólo con el uso de $\neg, \land, \lor$ ) donde $\neg$ sólo afecta a las variables proposicionales.

Answer 5

¿No es la "inducción fuerte" un ejemplo de esto? En lugar de demostrar $(\forall n) P(n)$ uno prueba $(\forall n)(\forall m \leq n) P(m)$ lo que da fuerza adicional a la hipótesis inductiva.