Comparing $2^n$ to $n!$ Comparing $\;2^n\;$ and $\;n!\;$
I need to rewrite one or the other so they can be more easily compared (i.e. have similar form). Because of the factorial, I'm a little lost as to how to compare the two functions. Normally, I would take the logarithm when trying to re-express a power like $2^n$, but I don't think this will work, since I don't know how to take the logarithm of a factorial, if at all. 
Might the series expansions of either functions be the right approach? If not could, someone point me in the right direction?
 A: By induction, $(n+1)!=(n+1) \cdot n! \geq (n+1) \cdot 2^n \geq 2 \cdot 2^n=2^{n+1}$ if $n! \geq 2^n$. Therefore, because $4$ is the smallest integer such that $2^n \leq n!$ is true, you deduce that $n! \geq 2^n$ for all $n \geq 4$.
A: \begin{align*}
2^n &= 2  \times  2  \times  \dots \times 2  \times  2 \times 2 \\
n! &= 1 \times  2  \times  \dots  \times  (n-2)  \times  (n-1) \times n
\end{align*}
Both of these expressions are $n$ numbers multiplied together. So for $n < 4$, $2^n > n!$ because the 1 in $n!$ adds nothing. However, for $n \geq 4$, $n!$ will always be larger than $2^n$, because the 4 in $4!$ is $2 \times 2$ so it compensates for the extra 2 in $2^n$, and all other terms $3,5,6,7,\dots$ are all larger than $2$.
A: Note that if $n\ge 2$ then
$$\frac{2^n}{n!} =\left(\frac{2}{1}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots+\frac{2}{n-1}\right)\cdot\left(\frac{2}{n}\right)=\left(\frac{2}{2}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots+\frac{2}{n-1}\right)\cdot\left(\frac{4}{n}\right).$$
The product $\frac{2}{2}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots\frac{2}{n-1}$ is $\le 1$. It follows that
$$\frac{2^n}{n!}\le \frac{4}{n}$$ 
when $n\ge 1$,
and therefore $\frac{2^n}{n!}\to 0$ as $n\to\infty$.
A: 
Normally, I would take the logarithm when trying to re-express a power like 2n,
  but I don't think this will work, since I don't know how to take the logarithm of a
  factorial, if at all. 

$\log(n!) = \log(1) + \log(2) + \log(3) + ... + \log(n)$
You can approximate the sum by integrating the log function from 1 to $n$.  Recall that the anti-derivative of the natural log is $x \ln{x} - x + C$.  From this, you get log(n!) = O(n log n).  Which is larger than $\log(2^n) = O(n)$.
If you're studying sorting algorithms in computer science, this is why comparison-based sorting algorithms (e.g., quicksort or mergesort) require O(n log n) time: These algorithm can be analyzed as a binary decision tree with $n!$ leaves (the possible permutations of the array).  Taking the (base-2) logarithm gives you the depth of the tree (if it's balanced), which equals the number of comparisons required.
A: Method 1: You can take a graphical approach to this problem:

It can be seen that the graphs meet at (0, 1), $2^x$ is greater until they intersect when $x \approx 3.459$, and then the factorial becomes much greater. Alternatively, plot $x! - 2^x$ to see a demonstration of the difference.
Method 2: use Stirling's approximation,
$$x! \sim \left(\frac{x}{e}\right)^x\sqrt{2\pi{x}}\left(1 + \frac{1}{12x}\right)$$
Now you can take logarithms of both expressions. Comparing the graphs of $y = x$ and the base 2 logarithm of the above expression, it can be seen that the latter quickly rises above the former.
A: $$2^n \;=\;\; \underbrace{\;2\cdot 2 \cdot  2\cdot 2\cdot\, \cdots \,\cdot 2 \; \cdot \;2\;}_{\text{n $ $factors of $2$}}$$
$$n! = \underbrace{1\cdot 2\cdot 3 \cdot 4\cdot\, \cdots\,\cdot (n - 1)\cdot n}_{\text{n factors}}$$
When we compare the products $\,$ factor-by-factor,$\,$ we can easily see that when $n \geq 4$, $\;n!\;>\;2^n$.  
This can, of course, be formalized using induction on $n$.
A: Consider for $n \ge 4$:
$$
2^n = 2 \cdot 2 \cdot 2^{n - 2} < 2 \cdot 3 \cdot 4 \cdot \ldots \cdot n = n!
$$
