# Using Induction to prove that $n^3log^4n=O(n^4)$

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.

• 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.) – David Richerby Mar 24 '17 at 13:04
• Indeed only curiosity. Thanks for the generalization of the proof, I like it a lot! – Lumon Mar 24 '17 at 13:34

## 2 Answers

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.

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.

• 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. – gnasher729 Mar 24 '17 at 22:20
• 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 – Lumon Mar 25 '17 at 10:42
• @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. – gnasher729 Mar 25 '17 at 23:52