1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Matt.P Jun 28 '18 at 22:25
  • $\begingroup$ 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$? $\endgroup$ – lhf Jun 28 '18 at 22:29
  • $\begingroup$ 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. $\endgroup$ – Matt.P Jun 28 '18 at 22:32
  • 1
    $\begingroup$ @lhf Yes, induction is needed. The proof by induction is exactly what you abbreviate with the dots. $\endgroup$ – egreg Jun 28 '18 at 22:35
  • $\begingroup$ And another one math.stackexchange.com/questions/76946/… $\endgroup$ – rtybase Jul 3 '18 at 17:28
3
$\begingroup$

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

In your second inequality

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

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

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

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.