0

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

Daniel
  • 6,999
Barbara
  • 1
  • Hi Barbara, welcome to MSE. Could you tell us please what you have tried to prove this without using a limit? where did you get stuck? – Daniel Jan 18 '17 at 05:00
  • @Daniel, Here is what I get stuck: $c*n^{0.57}+2017/n^{1.13}<n$ – Barbara Jan 18 '17 at 05:07
  • @Barbara What is your definition for $\omega(\cdot)$? Normally you'd be looking for something like $n^{0.14} - 2017 n^{-1.72} + n^{-3} \ge c$. – dxiv Jan 18 '17 at 05:12
  • @dxiv, here is what I did: $ cn^3<n^{3.41}-2017n^{1.28}$, becouse $n^{3.41}-2017n^{1.28}<n^{3.41}-2017n^{1.28}+1$ – Barbara Jan 18 '17 at 05:15
  • What is $\omega (n^3)$? This is not standard notation. – DanielWainfleet Jan 18 '17 at 05:25
  • @user254665 In the context, I assume that $\omega(\cdot)$ is the opposite of $o(\cdot),$, see this for example. The more standard notation would be $=\omega(n^3)$ rather than $\in \omega(n^3)$ though. – dxiv Jan 18 '17 at 05:27

1 Answers1

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 $$

dxiv
  • 76,497