Been trying to prove that $n! = \Omega(n^{100})$. I was approaching it with the solution below. I am not really sure my assumptions

125 Views Asked by At

We know that: $$f(n) = n! = \Omega (g(n)$$ if $$g(n) = O(f(n))$$ then, $$f(n) \in O(g(n))$$ If $$ f(n) \leq c \cdot g(n) \quad \textbf{for all $n\geq 1$}$$ then, assuming $n=1$ and $c=100^{100}$: $$n^{100} \leq 100^{100}\cdot n! \quad \textbf{for all $n\geq 1$}$$ \textbf{Base Case}: $n=1$ $$\therefore 1^{100} \leq 100^{100}\cdot 1! \quad\textbf{(true)}$$ \textbf{Induction Hypothesis}: Assume that for some arbitrary value, $n=k$, $k^{100} \leq 100^{100}\cdot k!$\ Induction Step: Showing for $n= k+1$ that: \begin{align} (k+1)^{100} &\leq 100^{100}\cdot (k+1)! \end{align} \begin{align} \Rightarrow (k)^{100} &\leq 100^{100}\cdot(k)! \nonumber \end{align} Multiplying both sides by $(k+1)$ so that the RHS looks exactly like Eqn. 1: \begin{align} \Rightarrow (k+1)(k)^{100} &\leq 100^{100}\cdot(k+1)(k)! \nonumber \\ (k+1)(k)^{100} &\leq 100^{100}\cdot(k+1)! \nonumber \end{align} N.B: For the LHS \begin{align} (k+1)(k)^{100} &< (k+1)(k+1)^{100} \nonumber \\ \Rightarrow (k)^{100} &< (k+1)^{100} \nonumber \end{align} Hence, \begin{align} \Rightarrow (k+1)(k)^{100} &< (k+1)(k+1)^{100} \leq 100^{100}\cdot(k+1)! \nonumber \\ \Rightarrow (k+1)(k+1)^{100} &\leq 100^{100}\cdot(k+1)! \nonumber \\ \Rightarrow (k+1)^{100} &\leq 100^{100}\cdot(k+1)! \nonumber \end{align} This proves: $$k^{100} \leq 100^{100}\cdot k! \quad \text{for all $n\geq 1$}$$ That means $n^{100} \leq 100^{100}\cdot n!$ for all values of $n\geq 1$.\\ Therefore, $$n^{100} \in O(n!)$$