How to prove that $n^{3.14}−2017n^{1.28}+1 \in ω(n^3)$ without using limit

Question

How to prove that $n^{3.14}−2017n^{1.28}+1 \in ω(n^3)$ without using limit?

Answer 1

Assuming the usual definition of $\omega(\cdot)\,$:

$n^{3.14}−2017n^{1.28}+1 = ω(n^3) \;\iff\; \forall c \gt 0 \; \exists N \gt 0 \;\big|\; n^{3.14}−2017n^{1.28}+1 \ge c\,n^3 \;\;\forall n \ge N$

The common, most direct way to prove that would be using limits, but since the OP specifically asked for an alternative proof without using limits, below is the outline of such a proof.

• Divide by $n^3$ and write the condition as:

$$ n^{0.14}\left(1 − \frac{2017}{n^{1.72}}\right)+\frac{1}{n^3} \;\ge\; c $$

• Find $N_1$ such that $1 − \frac{2017}{N_1^{1.72}} = \frac{1}{2}\,$, which is $N_1=\left(\frac{2017}{2}\right)^{1/1.72}\,$. By monotonicity of the LHS it follows that $1 − \frac{2017}{n^{1.72}} \ge \frac{1}{2}$ for $\forall n \ge N_1\;$ (1).   (Note that $\frac{1}{2}$ was an arbitrarily chosen constant, any other $\lambda \in (0,1)$ would have worked just as well for the rest of the argument.)

• Find $N_2$ such that $N_2^{0.14} = 2c\,$, which is $N_2 = (2c)^{1/0.14}\,$. Again by monotonicity of the LHS it follows that $n^{0.14} \ge 2c\,$ for $\forall n \ge N_2\;$ (2).

• Then for $\forall n \ge \max(N_1,N_2)\,$, by (1) and (2):

$$ n^{0.14}\left(1 − \frac{2017}{n^{1.72}}\right)+\frac{1}{n^3} \;\ge\; 2\,c \cdot\frac{1}{2} + \frac{1}{n^3} \;=\; c + \frac{1}{n^3} \;\gt\; c $$