# Big-Oh Notation Proofs

I'm studying Big-Oh Notation in my Discrete Structures class and I've proven most of the two questions that I've been assigned, although I'm stuck at one part on each.

So far in the class, we have not learned the induction method and are not allowed using graphs, limits or slopes of tangent lines to prove things. We can only use summations and algebraic calculations. Here is what I'm stuck on:

Note: The logarithms can be expressed with any base.

1. Proving $n!$ $\leq$ $n^n$ for all $n$ $\geq$ $2$

(Original question: Prove log$(n!) \in \Omega(n$log$(n))$ - I chose $c=1/2, n_0=2$)

1. Proving $3n^3-n^2+43 \geq \sqrt{n}^7$ for all $n \geq 9$

(Original question: Prove $2$log$(3n^3-n^2+43)\in O($log$(n))$ - I chose $c=7, n_0=9$)

I just can't figure out how to go about proving these things without using any of the methods listed above. If anyone has any idea where I could start, I would really appreciate some guidance!

• Not learnt the induction method? You cannot do without it in general. Besides, the sign in the first question must probably be reversed, and for that you don't require induction : note that $\sqrt n \leq n$ for all $n \geq 2$, and $1 \leq (n-1)!$ for all $n \geq 2$ and multiply these inequalities. Mar 17, 2018 at 5:07
• I suppose it was intended to be something like $\sqrt{n^n}$ Mar 17, 2018 at 5:56

For the first one you need to note $\log n! = \sum\limits_{i=1}^n \log i$
and $\sum\limits_{i = n/2}^n\log \frac{n}{2} \leq \sum\limits_{i = n/2}^n\log i \leq \sum\limits_{i=1}^n \log i$
For the second one you need to be large, i.e. $3n^3-n^2 + 43 \leq 47 n^3$ for all $n \geq 1$. And $\log 47n^3 = 3\log n + \log 47 \leq 4 \log n$ for $n \geq 6$.