Refutar $n \in \Omega(n^2)$

Question

Tengo una prueba que necesito para decir lo que está mal:

Demostraremos por inducción en $n$ que existe una constante $c > 0$ tal que para cada $n 4$ sostiene que $n c · n^2$

Caso base: para $n = 4$ , para $c = \frac{1}{4}$ se mantiene.

Hipótesis de inducción: Supongamos que la afirmación es correcta para $n1$ lo que significa que existe $c_1 > 0$ tal que $(n 1) c_1(n 1)^2$

Paso de inducción: Demostraremos que la prueba es correcta para $n$ : $n = n 1 + 1 c_1(n 1)^2 + 1 c_1 · (n^2 2n) c_1 · (n^2 \frac{n^2}{2}) = \frac{c_1}{2}·n^2$

La última desigualdad se debe a que para cada $n 4$ sostiene que $2n < \frac{n^2}{2}$ . Por lo tanto, tomando $c = \frac{c_1}{2}$ tenemos que $n c·n^2$ .

Creo que lo peor aquí, es que al tomar $c=\frac{c_1}{2}$ pero no estoy muy seguro de ello.

¿Alguna ayuda?

Gracias.

Answer 1

Sí, tomando $c=\frac c2$ es el problema aquí. Para ver eso, tenemos que ser más cuidadosos con lo que hacemos en la inducción.

Hay dos afirmaciones que podrías probar:

• Hay una $c>0$ , de modo que para todo $n\geq4$ , $n\geq cn^2$ .
• Para todos $n\geq4$ Hay un $c>0$ para que $n\geq cn^2$ .

Lo primero es lo que quieres, lo segundo es lo que ha demostrado tu inducción.

A grandes rasgos, hay que trabajar desde fuera hacia dentro. Así que si demuestras la primera afirmación, primero tienes que elegir algún $c$ (digamos que eliges $\frac14$ ). Y luego hay que demostrarlo:

• Caso base: Para $n=4$ tenemos $n\geq \frac14n^2$ . (Obras.)
• Paso de inducción (para $n\geq 4$ ): Si $n\geq \frac14n^2$ entonces $n+1 \geq \frac14(n+1)^2$ . (No funciona.)

Así que tu inducción se atasca tratando de probar esto.

Pero si intentas demostrar la segunda afirmación, tu inducción se ve un poco diferente. Tienes que demostrar:

• Caso base: Para $n=4$ existe un $c>0$ tal que $n\geq cn^2$ . (Obras, a saber $c=\frac14$ .)
• Paso de inducción (para $n\geq 4$ ): Si existe un $c>0$ tal que $n \geq cn^2$ entonces existe un $c>0$ tal que $n+1 \geq c(n+1)^2$ .

Ahora el paso de inducción funciona porque no es necesario ceñirse a un $c$ . En cambio, puede tomar el $c$ que existe por "existe un $c>0$ tal que $n \geq cn^2$ "y construir a partir de él un nuevo $c$ por "existe un $c>0$ tal que $n+1 \geq c(n+1)^2$ ", a saber $c_\mathit{new}:=\frac{c_\mathit{old}}2$ en su prueba.

Regla de oro: Todo lo que se cuantifica dentro del "forall $n$ " puede modificarse durante la inducción. Lo que se cuantifica fuera no puede.

Excepción: Cuando tenemos un cuantificador todo (por ejemplo, "forall $c>0$ , para todos $n\geq 4$ algo se sostiene") se puede ver a menudo que en las pruebas que la $c$ cambios en el paso de inducción (como hiciste en tu prueba)? ¿Por qué está permitido? Sencillo: si haces eso, en realidad estás demostrando "para todos $n\geq 4$ , para todos $c>0$ algo se sostiene" por mi argumento anterior. Pero eso es equivalente a "para todo $c>0$ , para todos $n\geq 4$ algo se sostiene" por las reglas de todos los cuantificadores. Así que está bien demostrar una cosa o la otra. (Pero si se quiere ser extremadamente formal, habría que decir explícitamente que se demuestra "para todo $c>0$ , para todos $n\geq 4$ algo se mantiene" y luego añadir otro paso de prueba para ir a "forall $c>0$ , para todos $n\geq 4$ algo se sostiene").

Answer 2

El problema es que no estás eligiendo la misma constante $c_1$ para todos los valores de $n$ que debería.

La definición es : $\exists c > 0 \, \forall n \, (n \geq c n^2)$

Su inducción sólo demuestra que $\forall n \, \exists c > 0 \, (n \geq c n^2)$ que es mucho más débil.

De hecho, aquí puede comprobar que $\frac{n}{n^2} = \frac{1}{n} \rightarrow_{n \rightarrow \infty} 0$ . Entonces, se puede razonar de la siguiente manera :

Si $f(n) \geq c g(n) > 0$ para todo (suficientemente grande) $n$ y $f(n), g(n) > 0$ y $\frac{f(n)}{g(n)} \rightarrow 0$ entonces $\lim\limits_{n \rightarrow \infty} \frac{f(n)}{g(n)} \geq c$ es decir $c \leq 0$ .