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

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$$

• It’s an easy induction on $n$. – Brian M. Scott Nov 27 '20 at 20:00
• Do you want a combinatorial interpretation? Base on your question you should tag it in combinatorics or combinatorial proofs. – Phicar Nov 27 '20 at 20:13

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.

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$$

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?

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

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.$$

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$$