# Prove by induction that $2^n\le (n+1)!$ for all $n\in\Bbb N$ [duplicate]

What I've done so far is prove for $n=1$:

$$2^1 \le (1+1)!$$ $$2 \le 2$$ Which is correct

Then I tried to prove for $n+1$, in other words, I want to get here:

$$2^{n+1}\le(n+2)!$$

So, I multiplied everything for 2:

$$2^n*2 \le2(n+1)!$$ $$2^{n+1} \le2(n+1)n!$$

So I already have what I wanted in the left part of the inequation, but I'm stuck for the right part. Can someone help me? Thanks

• So, your induction hypothesis is obviously that $2^k \leq (k+1)!$. You want to show that this implies $2^{k+1} \leq (k+2)!$. Well, $2^{k+1} = 2^k \cdot 2$, so using your induction hypothesis you can easily reason that $2^k \cdot 2 \leq (k+1)! \cdot 2$. Of course, $(k+2)! = (k+2)(k+1)!$. Is there any further you can say about the relationship between $k + 2$ and $2$? Well, $k \in \mathbb{N}$, so clearly $k+2 > 2$. That should complete the proof. – Matt.P Jun 28 '18 at 22:25
• Does one really need induction when it is clear that $(n+1)!= 1 \cdot 2 \cdot 3 \cdots n \cdot (n+1) \ge 1 \cdot 2 \cdot 2 \cdots 2 \cdot 2 = 2^n$? – lhf Jun 28 '18 at 22:29
• This is a good point, lhf. Many of my professors have argued as much. In fact, one of them said that if I'm tempted to use ellipses, I should erase what I wrote and start writing a proof by induction. But I think your point is completely valid. – Matt.P Jun 28 '18 at 22:32
• @lhf Yes, induction is needed. The proof by induction is exactly what you abbreviate with the dots. – egreg Jun 28 '18 at 22:35
• And another one math.stackexchange.com/questions/76946/… – rtybase Jul 3 '18 at 17:28

hint if n is a positive integer then $(n+2)!\geq (n+1)!$so that $(n+2)(n+1)!\geq2(n+1)!$

Btw that 2 comes from an easy proof by developping the parenthesis. Now use

($a<b<c\implies a<c$)

• agreed but... i don't know how to get to (n+2)! – Agapita Jun 28 '18 at 22:32
• See the edit man – T.D. Jun 28 '18 at 22:38
• ok man, got it. – Agapita Jun 28 '18 at 22:41
• You're welcome please accept my answer – T.D. Jun 28 '18 at 22:47

Hint: $$2\,(n+1)!<(n+2)\,(n+1)!=(n+2)!$$

• It should be $\le$, not $<$. – egreg Jun 28 '18 at 22:34
• @egreg: I supposed $n\ge 1$, as often students follow the convention that $\mathbf N$ starts at $1$. – Bernard Jun 28 '18 at 23:10

Since a hint has already been provided, I am supplying a combinatorial approach. There are $(n+1)!$ permutations on the set $\{0,1,2,\ldots,n\}$. Amongst these, consider permutations $\sigma$ such that, for any $k=0,1,2,\ldots,n$, there exists $j_k\in\{0,1,2,\ldots,n-k\}$ such that $\sigma$ maps $\{0,1,2,\ldots,k\}$ to $\left\{j_k,j_k+1,\ldots,j_k+k\right\}$. Show that there are $2^n$ such permutations.

An Example: Take $n=2$, and represent permutations as juxtapositions of labels $0$, $1$, and $2$. Then, amongst all six permutations $012$, $021$, $102$, $120$, $201$, and $210$, only four of them ($012$, $102$, $201$, and $210$) are the special permutations we consider.