It stands to reason that $n^2+n \in \Theta(n^2)$.
But how can I formally proof it?
I tried next way:
Generalized to $$f(n)+o(f(n)) \in \Theta(f(n))$$
Separated to
$$\tag{1} f(n)+o(f(n)) \in O(f(n))$$
$$\tag{2} f(n)+o(f(n)) \in \Omega(f(n))$$
Definitions of asymptotics says:
$o(g(n))$ = { $f(n)$: for any positive constant $c > 0$, there exists a constant $n_0 > 0$ such that $0 \leq f(n) < cg(n)$ for all $n \geq n_0$ }
$O(g(n))$ = { $f(n)$: there exists positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0$ }
$\Omega(g(n))$ = { $f(n)$: there exists positive constants $c$ and $n_0$ such that $0 \leq cg(n) \leq f(n)$ for all $n \geq n_0$ }
For $o(f(n))$ introduce $f'(n), c', n'$ so that $$\tag{3} 0 \leq f'(n) < c'f(n)$$, for all $n \geq n'$
For $(1)$ we must show that $$0 \leq f(n) + f'(n) \leq cf(n)$$
$$(3) \implies f(n) + f'(n) < f(n) + c'f(n) \leq cf(n)$$, for $c \geq c'+1$
For $(2)$ we must show that $$0 \leq cf(n) \leq f(n) + f'(n)$$
And at this point I stuck.
Where did I make mistake?
Is my reasoning correct at all?
Thanks.
Update
We can simply take $c=1$ ans as $f'(n) \geq 0 $
$$ cf(n) \leq f(n) + f'(n)$$
Thank you Kevin.
Best Answer
You're doing this more abstractly than is strictly necessary. All we need to show is that $n^2+n$ is bounded above by $k_1n^2$ for some $k_1$, once $n$ is big enough, and below by $k_2n^2$ for some $k_2,$ similarly. Take $k_2=1$. Then $n^2+n\geq n^2$ for all $n$. Now, what do we get from $k_1=2$?
However, as long as you're proving the more general fact you passed to: your (1) is fine. For (2), why not take $c=1$?