Supongamos que tenemos funciones $f,n : \mathbb{N} \rightarrow \mathbb{R}_{> 0} $ .
Demuestre que para valores $n_0,c \in \mathbb{N} \ \ \forall n \geq n_0$ es cierto lo siguiente
$$ | f(n) - g(n) | \leq cn \implies f \in \Theta(g)$$
He visto un par de definiciones de $\Theta(f)$ este es el que se me permite usar:
$g \in \Theta(f) \iff g \in \mathcal{O}(f) \land f \in \mathcal{O}(g) $ y no creo que se me permita usar la definición con las dos constantes ( de $\Theta$ es decir)
He intentado lo siguiente pero no he podido llegar más lejos. Creo que he dado algunos pasos en la dirección correcta pero no veo nada.
$$wlog \ \ f(n) > g(n) $$ $$ f(n) + cn \leq g(n) $$
$$f(n) -g(n) \leq \delta := c_1 f(n) - c_2g(n) \quad c = max(c_1,c_2) $$
$$ \delta \leq c(f(n) - g(n) ) $$
$f(n) - g(n) $ podría ser potencialmente "recortado" con aritmética modular para que el resto quepa en menos de $n$ y poniendo el resto en nuestro $c$ .
He intentado jugar con estos pequeños fragmentos pero como he dicho no he podido llegar más lejos.
Descargo de responsabilidad:
Esta es una pregunta de tarea, por favor no publique las respuestas completas, una vez que tenga la solución calificada la publicaré aquí. Creo que he hecho mi parte justa de pensamiento en la tarea y he demostrado lo que sé y lo que no sé. Creo que merezco una pista en este punto.
