La prueba de que $n^2 < 2^n$

Question

¿Cómo puedo probar la siguiente declaración por inducción?

$$n^2 \lt 2^n$$

$P(n)$ es la declaración de $n^2 \lt 2^n$

Reclamo: Para todos los $n \gt k$ donde $k$ es cualquier entero, $P(n)$

(desde $k$ es cualquier entero, supongo que tengo que probar esto de números enteros positivos y negativos)

Así que vamos con el caso base se $P(1)$, y tengo que probarlo $P(n)$ $n \ge 1$ $n \lt 1$

$P(1)$ $1^2 \lt 2^1$ que es claramente cierto.

Inducción de la hipótesis: $k^2 \lt 2^k$

Inductivo paso $(k+1)^2 \lt 2^{(k+1)}$

$(k+1)^2 = k^2 + 2k + 1$

$k^2 + 2k + 1 \lt 2^k + 2k + 1$ por hipótesis inductiva

No está seguro de cómo proceder. Es mi intuición que tengo que probar esto de $n \ge 1$ $n \lt 1$ correcto?

Answer 1

Sugerencia solamente: Para $n \geq 3$ $n^2 > 2n + 1$ (esto no debería ser difícil de ver) así que si $n^2 < 2^n$, a continuación, considere la posibilidad de $$ 2^{n+1} = 2\cdot2^n > 2n^2 > n^2 + 2n+1 = (n+1)^2. $$ Ahora esto significa que la inducción paso "funciona" cuando jamás $n\geq 3$. Sin embargo, para iniciar la inducción necesitas algo mayor que tres. Por juicio un error, usted puede encontrar el más pequeño $n(\geq0)$ tal que $n^2 < 2^n$.

Answer 2

$$n^2<2^n\Longleftrightarrow 2\log n<n\log 2\Longleftrightarrow\frac{\log n}{n}<\frac{\log 2}{2}$$

Pero sabemos que $\,\displaystyle{\frac{\log n}{n}\xrightarrow[n\to\infty]{}0}\,$ , por lo que la desigualdad anterior es definitivamente verdadero de uno definitivo índice $\,n\,$ y en...pero no para todos los productos naturales!

Answer 3

Si desea utilizar la inducción, supongo que has comprobado en el caso base $n = 5$. Para hacer el paso inductivo, supongamos que la declaración tiene para algunos $k$: $k^2 < 2^k$, y, a continuación, bajo este supuesto, usted quiere verificar que la declaración tiene por $k+1$: $(k+1)^2 < 2^{k+1}$. Bien,

$$ (k+1)^2 = k^2 + 2k + 1 < 2^k + 2k + 1 $$

por la hipótesis inductiva. Cuando se $2^k + k + 1 < 2^{k+1}$. Bien,

$$\begin{align} 2^k + k + 1 < 2^{k+1} &\iff k+1 < 2^{k+1} - 2^k \\ &\iff k+1 < 2^k. \end{align}$$

Es suficiente para mostrar que $k+1 < 2^k$ todos los $k \geq 5$. Una manera de hacer esto es mediante la inducción. Se puede mostrar fácilmente el caso base $5 + 1 < 2^5$. Ahora, supongamos que se cumple para algunos $j \geq 5$, y queremos demostrar que también tiene por $j+1$. Por lo tanto, queremos mostrar que si $j+1 < 2^j$,$(j+1) + 1 < 2^{j+1}$. Esta de la siguiente manera casi inmediata, ya que

$$ (j+1) + 1 < 2^j + 1 < 2^j + 2^j = 2^{j+1} $$ Debe tener en cuenta que la desigualdad de $1 < 2^j$ no es cierto en general, pero es cierto para $j > 1$ (y, en particular, para $j \geq 5$). Por lo tanto, hemos demostrado que $k+1 < 2^k$ todos los $k \geq 5$, y esto era precisamente lo que necesitábamos para el paso inductivo de la prueba original.

Cabe señalar que la inducción no es realmente la manera más fácil de probar esta desigualdad, pero si queremos estrictamente el uso de la inducción, entonces algo como esto prueba (y la consiguiente prueba de la declaración de $k+1 < 2^{k}$$k \geq 5$) es el camino a seguir.

Como nota final, para mostrar lo que quiero decir acerca de los más fáciles de la prueba, como se señaló anteriormente, tenemos $n^2 < 2^n$ si y sólo si $\frac{\log n}{n} < \frac{\log 2}{2}$. Ahora, $f(x) = \frac{\log(x)}{x} \implies f'(x) = \frac{1 - \log x}{x^2} < 0$ al $x > e$. Por lo tanto, la función es estrictamente decreciente para $x > e$. Junto con el hecho de que $f(x) \to 0$$x \to \infty$, entonces es suficiente para encontrar el primer entero $t$ tal que $\frac{\log t}{t} < \frac{\log 2}{2}$. Esto pasa a ser $t = 5$.

Añadido: Thomas' sugerencia es un poco mejor que mi propia respuesta, ya que sólo requiere la verificación de los valores por los que $n^2 > 2n +1$, lo que se puede hacer con el álgebra elemental.

Answer 4

Su declaración sólo es cierto para $n=0$, $n=1$ y $n \geq 5$.
Que comienzan con $n=5$, esto le da a $5^2=25 < 2^5 = 32$

Así que Supongamos que es cierto para $n$. Que sabemos que $$2^{k+1}= 2 \cdot 2^k > 2 k^2>k^2+2k+1=(k+1)^2$$ (como $n^2>2n+1$ todos los $n\geq 3$, y como empezamos con $n=5$ esto siempre es cierto)

Answer 5

Como un hecho de la diversión de otra manera a ver que esta desigualdad es verdadera, finalmente, es comparar la suma de los números en la $n-1$ 'st fila del triángulo de pascal a la $n$'th triangular número que aparece en la $n+1$ 'pt de la fila y se produce a lo largo de la diagonal del triángulo de pascal. Visite el enlace para más detalles, http://mathforum.org/workshops/usi/pascal/pascal_triangular.html. El hecho se presentó en esa página, más el hecho de que la suma de la fila del triángulo de pascal es una potencia de dos que puede ser usado para demostrar la deseada desigualdad.

Esto equivale a probar que $\frac{n(n+1)}2 \lt 2^\left(n-1\right)$ que es más fuerte que la desigualdad original, ya que $n^2 \lt n(n+1)$$n \gt 0$ .