AALIE

Demostraciones Completas — Teorema de Límites

Criterio general de límites y tres demostraciones completas de pertenencia asintótica.

7. Demostraciones completas — Teorema de límites

Teorema general

Teorema: Criterio de los límites para notaciones asintóticas

Sea $L = lim_{n \to \infty} \frac{f ( n )}{g ( n )}$ (Convención A). Entonces:

Criterio de límites con Convención A

Resultado del límite	Conclusión
$L = 0$	$f \in o (g)$ y $f \in O (g)$
$0 < L < \infty$	$f \in Θ (g)$ y también $O$ , $Ω$
$L = 1$	$f \sim g$ y también $Θ$ , $O$ , $Ω$
$L = + \infty$	$f \in ω (g)$ y $f \in Ω (g)$

Con Convención B ( $lim g / f = L^{'}$ ), el mismo cuadro pero con $0$ y $\infty$ intercambiados:

Criterio de límites con Convención B

Resultado del límite	Conclusión
$L^{'} = 0$	$f \in ω (g)$ y $f \in Ω (g)$
$0 < L^{'} < \infty$	$f \in Θ (g)$
$L^{'} = 1$	$f \sim g$
$L^{'} = + \infty$	$f \in o (g)$ y $f \in O (g)$

Caso oscilatorio

El alcance declarado del módulo incluye el caso oscilatorio. Si el límite no existe por oscilación, este criterio directo no permite concluir automáticamente una pertenencia a $O$ , $Ω$ , $Θ$ , $o$ , $ω$ o $\sim$ solo por la tabla; se debe volver a las definiciones o usar otra herramienta.

Demostración 1: 3n² + 5n ∈ Θ(n²)

Demostrar que $3 n^{2} + 5 n \in Θ (n^{2})$ .

Paso 1 — Calcular el límite (Conv. A)

Plantear el límite

n \to \infty lim \frac{3 n ^{2} + 5 n}{n ^{2}}

Dividir cada término del numerador entre n²

n \to \infty lim (\frac{3 n ^{2}}{n ^{2}} + \frac{5 n}{n ^{2}})

Simplificar

n \to \infty lim (3 + \frac{5}{n})

Evaluar

3 + 0 = 3

Paso 2 — Aplicar el teorema

$L = 3$ , que es una constante positiva finita $(0 < 3 < \infty)$ . Por el teorema, esto implica $f \in Θ (n^{2})$ .

Paso 3 — Verificación con definición formal

Tomamos $c_{1} = 3$ y $c_{2} = 4$ , y buscamos $n_{0}$ tal que:

3 n^{2} \leq 3 n^{2} + 5 n \leq 4 n^{2} para todo n \geq n_{0}

La desigualdad izquierda $3 n^{2} \leq 3 n^{2} + 5 n$ es siempre verdadera para $n \geq 0$ .
La desigualdad derecha $3 n^{2} + 5 n \leq 4 n^{2}$ equivale a $5 n \leq n^{2}$ , es decir $n \geq 5$ .

Conclusión

Tomando $n_{0} = 5$ , la propiedad se cumple para todo $n \geq 5$ .

Demostración 2: n ∈ o(n²)

Demostrar que $n \in o (n^{2})$ .

Convención A — Paso 1

n \to \infty lim \frac{n}{n ^{2}} = n \to \infty lim \frac{1}{n} = 0

Convención B (curso) — Paso 1

n \to \infty lim \frac{n ^{2}}{n} = n \to \infty lim n = + \infty

Paso 2 — Aplicar el teorema

Conv. A: $L = 0 \Rightarrow f \in o (g)$ . Conv. B: $L = \infty \Rightarrow f \in o (g)$ (criterio del curso). Ambas concluyen $n \in o (n^{2})$ .

Paso 3 — Verificación con definición

Debemos mostrar que para toda $c > 0$ , existe $n_{0}$ tal que $n < c \cdot n^{2}$ para $n \geq n_{0}$ .

Partimos de la desigualdad

n < c \cdot n^{2}

Dividimos por n positivo

1 < c \cdot n

Despejamos n

n > \frac{1}{c}

Conclusión

Tomando $n_{0} = ⌈ \frac{1}{c} ⌉ + 1$ , se cumple para todo $n \geq n_{0}$ .

Demostración 3: n² ∈ ω(n)

Demostrar que $n^{2} \in ω (n)$ .

Convención A — Paso 1

n \to \infty lim \frac{n ^{2}}{n} = n \to \infty lim n = + \infty

Convención B (curso) — Paso 1

n \to \infty lim \frac{n}{n ^{2}} = n \to \infty lim \frac{1}{n} = 0

Paso 2 — Aplicar el teorema

Conv. A: $L = \infty \Rightarrow f \in ω (g)$ . Conv. B: $L = 0 \Rightarrow f \in ω (g)$ . Ambas concluyen $n^{2} \in ω (n)$ .

Alcance de la demostración en el documento

En esta tercera demostración, el documento cierra con la aplicación del teorema. No incluye una verificación adicional con la definición formal, a diferencia de las demostraciones 1 y 2.