How to prove that $n!>2^n$ holds for all $n>3$?

Question

I suspect something with sets since one with cardinality $n$ has $n!$ permutations and its powerset contains $2^n$ elements. It could also involve binomial coefficients because of$$\begin{pmatrix}n\\0\end{pmatrix}+\begin{pmatrix}n\\1\end{pmatrix}+\begin{pmatrix}n\\2\end{pmatrix}+\cdot\cdot\cdot+\begin{pmatrix}n\\n\end{pmatrix}=2^n$$

Answer 1

If $n!>2^n$ multiply both sides by $(n+1)$ to get $$ (n+1)!>(n+1)2^n> 2 \times 2^n > 2^{n+1} $$ with minor details to be filled.

Answer 2

The number $n!$ is the product of the $n-1$ numbers $2,3,\ldots,n$, each of which is greater than or equal to $2$ (and all of them but $2$ is actually greater than $2$) and, since $n>3$, at least one of them is greater than or equal to $4$. So, $n!>2^{n-2}\times4=2^n$

Answer 3

I think it's simpler than you're suggesting. Are you familiar with proof by induction? Here's a hint: once you know that $4! > 2^4$, look at how you get from $4!$ to $5!$ and from $2^4$ to $2^5$. If you can prove it for $n = 5$ given that it's true for $n = 4$, can you continue that process?

Answer 4

multiply both sides by n+1 Then prove that $(n+1)!2^n$ is greater than $2^{n+1}$

Answer 5

The OP was not very clear if them were looking for a combinatorial interpretation, in such case:

Consider the following function $Fix : S_n\longrightarrow P([n]),$ called the set of fixed points of a permutation, where $S_n$ is the set of permutations on $[n]$ and $P([n])$ is the powerset of $[n],$ defined as $$Fix(\pi)=\{i: \pi(i)= i \},$$ for some permutation $\pi ,$ meaning we are recording the fixed points of the permutation.

Notice that if we fix $n-1$ points in the permutation, we are fixing $n$ because there is no space to make the$ n-$th element not fixed. So any set $A\subseteq [n]$ such that $|A|=n-1$ is not the set of fixed points of any permutation. So, apriori, $$n!=|S_n|\geq 2^n-n+1.$$ We actually can say more, using the Derangements(permutations without fixed points, denoted by $D_m$) we can decompose $S_n$ in the statistic of how many fixed points the permutation has i.e., $$n!=\sum _{k=0}^n\binom{n}{k}D_{n-k}=\sum _{k=0}^{n-2}\binom{n}{k}D_{n-k} +1,$$ where the last equality is by the argument above on how there are no permutations that fix $n-1$ points exactly. Now, notice that $D_{n-1}>2$ iff $n>3,$ because $D_k>D_{k-1}$ for $k>1$ (why? ). So we can split this as $\binom{n}{1}D_{n-1}=\binom{n}{1}+\binom{n}{1}(D_{n-1}-1)=\binom{n}{n-1}+\binom{n}{1}(D_{n-1}-1).$ So we have that $$n!=\sum _{k=0}^n\binom{n}{k}D_{n-k}=\sum _{k=0}^{n-2}\binom{n}{k}D_{n-k} +1=D_n+\binom{n}{1}(D_{n-1}-1)+\sum _{k=2}^{n-2}\binom{n}{k}D_{n-k}+\binom{n}{n-1} +1>\sum _{k=0}^n\binom{n}{k}=2^n.$$

Answer 6

Since $n\ge 4$ we have $n! = 1\cdot 2\cdot 3\cdot 4 \cdot 5\cdots n = 24 \cdot 5 \cdots n > 16 \cdot 5 \cdots n\ge 2^4\cdot 2 \cdots 2 = 2^42^{n-4}=2^n$