0

How to prove that $n!=O(5^n)$ is false?

I tried to use mathematical induction, but I wasn't able to find any results.

user2134
  • 13

1 Answers1

2

Just observe that, using $a_n=\frac{n!}{5^n}$,

$$\lim_{n\to \infty}\left|\frac{a_{n+1}}{a_n}\right|=\lim_{n\to \infty}\frac{(n+1)!5^{n}}{n!5^{n+1}}=\lim_{n\to \infty}\frac{n+1}{5}=\infty,$$ thus $\lim_{n\to \infty}a_n=\infty$ so that we cannot possibly have $\frac{n!}{5^n}\leq C$ for a $C\in\mathbb{R}$ as $n\to\infty$.

Václav Mordvinov
  • 3,268
  • Why did you use $\frac{a_{n+1}}{a_n}$? And is there another way to solve it? Because my professor didn't mention the limits approach, he uses the definition of big-oh notation instead. So we have to find some constants $c, n_0$ such that $\forall n \geq n_0, n!\leq c5^n$. – user2134 Mar 28 '18 at 22:11
  • The limit tends to infinity, so for all $C$ there exists $N$ such that $n>N$ implies $n!>C5^n$. We want to show $n!/5^n$ is bounded when we want to say $n!=O(5^n)$, but by showing $n!/5^n$ is unbounded above, I show $n!\neq O(5^n)$. – Václav Mordvinov Mar 29 '18 at 05:08