Prueba de $n^2 \leq 2^n$ .

Question

Estoy tratando de demostrar que $n^2 \leq 2^n$ para todos los naturales $n$ con $n \ne 3$ .
Mis pasos son:

• caso base de inducción: $n=0:$ $0² \leq 2$ que está bien.
• paso inductivo: $n \rightarrow n+1:$ $(n+1)²\leq2^{n+1}$ $$(n+1)^2 = n^2 + 2n + 1 = ...help...\leq 2^{n+1}$$

Conozco la desigualdad de bernoulli pero no sé dónde usarla, si es que la necesito. Tengo problemas cuando se trata de demostrar cosas que se basan en órdenes..

Answer 1

Primero porque hay que tener $n\neq 3$ la base de inducción debe ser $n=4$ . Para el paso de inducción: Supongamos que $n^2\le 2^n$ . Entonces, $$(n+1)^2=n^2+2n+1\le 2^n+2n+1\le 2^n+2^n=2^{n+1}$$ porque $2n+1\le 2^n$ para $n\ge 3$ (¿por qué es esto cierto?).

Si hubieras empezado con la base inductiva $0,1$ o $2$ entonces habrías tenido problemas porque $2n+1\le 2^n$ no es válida para $n=2$

Prueba de $2n+1\le 2^n$ para $n\ge 3$ .

Base de inducción: Para n=3, $$2\cdot 3+1=7\le 8=2^3$$ Paso de inducción: Supongamos que para $n\ge 3$ , $2n+1\le 2^n$ . Entonces $$2(n+1)+1=2n+1+2\le 2^n+2\le 2^n+2^n=2^{n+1}$$ y así hemos terminado

Answer 2

Una prueba del tipo de análisis.

$x^{1/x}$ tiene su máximo en $x = e$ y está aumentando para $1 < x < e$ y disminuyendo para $x > e$ .

$2^{1/2} = 4^{1/4}$ , así que $x^{1/x} < 2^{1/2}$ para $x > 4$ o $x^2 < 2^x$ para $x > 4$ .

Me sorprende que esto haya funcionado tan bien.

Generalización obvia: Si $x > e$ y $y$ satisface $1 < y < e$ y $y^{1/y} = x^{1/x}$ entonces $z^{1/z} < y^{1/y}$ para $z > x$ o $z^y < y^z$ para $z > x$ .

Answer 3

Otra posibilidad es escribir $$2^n = \sum\limits_{k=0}^n C_n^k \geq 1+n+ \frac{n(n-1)}{2} + \frac{n(n-1)(n-2)}{6} \geq n^2$$ para $n \geq 5$ . Puede interpretarse como sigue: el conjunto $\{1,...,n\}$ tiene al menos $n^2$ subconjuntos de cardinalidad a lo sumo tres, y exactamente $2^n$ subconjuntos; por lo tanto, $2^n \geq n^2$ .

Answer 4

Aquí hay otra prueba analítica. Primero hay que tener en cuenta que $$\frac{2}{\operatorname{log}{2}}\operatorname{log}{4}=4.$$ El valor de $2/\operatorname{log}{2}$ es un poco menos que $3$ . ( Prueba. $\frac{2}{\operatorname{log}2}<3\Leftrightarrow 2<3\operatorname{log}2\Leftrightarrow e^2<e^{3\operatorname{log}2}=8$ lo cual es claramente cierto ya que $e<2.75=\frac{11}{4}$ . $\square$ ) Así, para $n>4$ , $$\frac{d}{dn}\left(\frac {2} {\operatorname{log} {2}}\operatorname{log} {n}\right) = \frac {2} {\operatorname{log}{2}}\frac{1}{n} <1=\frac{d}{dn}\left(n\right).$$ Así, $\frac{2}{\operatorname{log}{2}}\operatorname{log}{n}\leq n$ para $n\geq 4$ por el principio del hipódromo . Equivalentemente, $\log_2 n^2 \leq \log_2 2^n$ de la que obtenemos $n^2\leq 2^n$ .