Using $1+x\leq e^x$ to show that $(n+o(n))^k=\Theta(n^k)$ (CLRS)

Question

I'm working through the 4th edition of CLRS, and I'm having difficulties understanding how to solve one of the exercises(p. 70, exercise 3.3-3) (Actually, after that exercise they are all problematic for me):

3.3-3
Use equation (3.14) or other means to show that $(n+o(n))^k=\Theta(n^k)$ for any real constant k. Conclude that $\lceil n\rceil ^k=\Theta (n^k)$ and $\lfloor n\rfloor^k=\Theta (n^k)$

Equation 3.14 is: $1+x\leq e^x$ for any real x

My attempt:

On page 58, in the Asymptotic notation in equation and inequalities section, the author write:

In some cases, asymptotic notation appears on the left-hand side of an equation, as in
$2n^2+\Theta(n)=\Theta(n^2)$
Interpret such equations using the following rule: No matter how the anonymous functions are chosen on the left of the equal sign, there is a way to choose the anonymous functions on the right of the equal sign to make the equation valid.

Also they write:

The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation appears.

Based on these rules my understanding of problem lead me to to this:

$$ (n+o(n))^k = \Theta(n^k) \Rightarrow \\ (n+f_1(n))^k = \Theta(f_2(n)) $$ Where $o(n)$ is $o(f_1(n))$ which is transformed in $$0\leq f(n) < c_1g_1(n)$$ and $\Theta(n^k)$ is $\Theta(f_2(n))$ which is transformed in $$0\leq c_2g_2(n)\leq f_2(n) \leq c_3g_3(n)$$ with possibility of merging these two equations into $$0\leq c_2g_2(n)\leq f(n) \leq c_3g_3(n) < c_1g_1(n)$$ But I am not sure that it's the right thing to do, more like I misread multiple times some basic understanding of how it works on previous pages in that chapter.

I do understand that original equation perfectly explained by first rule, but I can't understand how I can show that this equation is equal, especially using something like $1+x \leq e^x$

---

In summary, I would greatly appreciate any effort to explain what I am missing and, if possible, an explanation for 5y.o., because I am pretty "nooby" in asymptotic functions and how they are used.

Thanks.

EDIT: I didn't write the definition of o and $\Theta$, so I'll write them like they were written in the book:

$o(g(n))=\{f(n):$ for any positive constant $c>0$, there exists a constant $n_0$ such that $0\leq f(n) < cg(n)$ for all $n\geq n_0\}$

$\Theta(g(n))=\{f(n):$ there exist positive constants $c_1,c_2$ and $n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0\}$

Also, there is theorem that says:

For any two functions $f(n)$ and $g(n)$, we have $f(n)=\Theta(g(n))$ if and only if $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$

So, I must write definition for $\Omega$ too:

$\Omega(g(n))=\{f(n):$ there exist positive constants $c$ and $n_0$ such that $0 \leq cg(n) \leq f(n)$ for all $n \geq n_0$

Answer 1

You don't define $o$ and $\Theta$ but I do assume they correspond to the $o$ and $O$ notation on this wikipedia page.

I prefer to start from scratch. If you want to prove that $$ (n+ o(n))^k \le \Theta(n^k)$$ you should translate that statement back to the definitions. The left hand side is a placeholder for $$ (n+ f(n))^k$$ where $f=o(n)$, i.e. for every $\epsilon > 0 $ there is a constant $N_0 > 0$ such that $|f(n)|\le \varepsilon n $ if $n\ge N_0$. This implies $\frac{f(n)}{n}\le \varepsilon$

Now we make use of the hint and rewrite $$(n+ f(n))^k = n^k (1+\frac{f(n)}{n})^k \le n^k(1+\varepsilon)^k \le n^k (e^\varepsilon)^k $$

Now if you look closely at the right hand side of this inequality and compare with the definition of an expression being $\Theta(n^k)$ you will see we are done. We can just choose $\varepsilon =1$, set $M:=e^k $ and have shown that for this choice of $\varepsilon$, if $n\ge N_0$, $$(n+o(n))^k = (n+f(n))^k \le M n^k = \Theta(n^k)$$