Proof of big-O notation

Question

Prove the following:

1. If f is a polynomial of degree $d$, then $f(n)=O(n^{d})$.
2. For every $d \in N, n^{d} = O(e^{n})$

Intuitively, it makes sense to me that for the first one, growth order depends on the term with the highest power and for the second one, exponential growth grows faster than anything else. I'm not quite sure how to prove this, though. I tried to use induction on the first one but I ended up just making a circular argument.

Answer 1

1. Given two real valued functions f and g: $$f(n)=O(g(n))$$ If $c>0$ and $n_0>0$: $f(n) \geq cg(n) \geq 0, \forall n\geq n_0$

From the definition it follows that for $n \geq 0$

$$a_0n^d + a_1n^{d-1} + a_2n^{d-2} + ... + a_d \leq |a_0|n^d + |a_1|n^{d-1} + |a_2|n^{d-2} + ... + |a_d|$$

$$\leq |a_0|n^d + |a_1|n^{d} + |a_2|n^{d} + ... + |a_d|n^{d}$$ $$\leq n^d(|a_0| + |a_1| + |a_2| + ... + |a_d|)$$ Let $c=|a_0| + |a_1| + |a_2| + ... + |a_d|$ and $n_0=1$ $$\Rightarrow g(n)\equiv n^d$$ $$\Rightarrow f(n)\equiv O(n^d)$$