1
$\begingroup$

I need to prove the following asymptotic relation for the purpose of cacluating a recurrence relation: $$n^3log^4n=O(n^4)$$ I tried and failed to do it with induction, which, if possible using basic Calculus 1 level math, I would like you to help me with. I am not required to do it with induciton or anything, I just wondered if I can do it.

I was able to prove it though, in a differet manner: $$f \in o(g) \Rightarrow f \in O(g)$$ $$lim_{n\to \infty} \frac{n^3log^4n}{n^4}=0$$ Using L'Hôpital's rule 4 times, which proves that: $$n^3log^4n=o(n^4)$$ By the definitino of $o$.

Therefore it also follows that $$n^3log^4n=O(n^4)$$

For the basis of the induction let $n=1$ and with $c=1$: $$f(1) = 1^3log^4(1) = 0 \leq 1=1^4 \cdot 1=c \cdot g(1)$$ From here I think that it would be enough to show that: $$log^4(n) \leq n$$ Although I am not sure how to continue from here.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I don't really see why you want to prove it by induction. I guess it's just curiosity but, still, what would you learn from an inductive proof? Probably it's possible but induction isn't necessarily a sensible way to prove every property of the natural numbers. (By the way, it's easier to use L'Hôpital once to prove that $\log n = o(n^c)$ for all $c>0$ and then you know that $\log^4 n = o((n^{1/4})^4) = o(n)$. Indeed, unless you're specifically asked to prove it, you can just use $\log n=o(n^c))$ for all $c$ as a canned fact.) $\endgroup$
    – David Richerby
    Commented Mar 24, 2017 at 13:04
  • $\begingroup$ Indeed only curiosity. Thanks for the generalization of the proof, I like it a lot! $\endgroup$
    – Lumon
    Commented Mar 24, 2017 at 13:34

2 Answers 2

Reset to default
1
$\begingroup$

You showed that f (n) = o (g (n)). That's it. There is nothing else to prove.

If you look at the definition of o (f (n)) and O (f (n)), they are almost identical except one says "for every eps > 0" and the other says "there is one c > 0". You can take every single eps of the little-o definition and use it as the c in the big-O definition.

Improve this answer
$\endgroup$
1
$\begingroup$

You already have your induction basis: $$f(1) = 1^3log^4(1) = 0 \leq 1=1^4 \cdot 1=c \cdot g(1)$$

Now you need to apply the induction step. Suppose $$n^3log^4n\leq c \cdot n^4$$

Then prove: $$(n+1)^3log^4(n+1)\leq c \cdot (n+1)^4$$

and your proof by induction will be completed.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Good luck with the induction step. If c = 1 and log is taken to be base 2, the statement is false for 3 ≤ n ≤ 65,535. $\endgroup$
    – gnasher729
    Commented Mar 24, 2017 at 22:20
  • $\begingroup$ Yes, I can form the induction step, proving it though is the problem, maybe what @gnasher729 said was the problem, a bad choice for c $\endgroup$
    – Lumon
    Commented Mar 25, 2017 at 10:42
  • $\begingroup$ @Lumon: The problem is not that you cannot prove it, the problem is that for small n the induction step itself is actually false, independent of c. For small n, the left hand side grows faster than the right hand side. $\endgroup$
    – gnasher729
    Commented Mar 25, 2017 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.