$n! \leq \left( \frac{n+1}{2} \right)^n$ via induction

I have to show $n! \leq \left( \frac{n+1}{2} \right)^n$ via induction.

This is where I am stuck:

$$\left( \frac{n+2}{2} \right)^{n+1} \geq \dots \geq =2 \left( \frac{n+1}{2} \right)^{n+1} = \left( \frac{n+1}{2} \right)^n(n+1) \geq n!(n+1) = (n+1)! $$

I approached this from both sides and this is the closest I can get. I realize that $n+2$ on the left has to be bigger than $n+1$ on the right, but I do not know who to show that it overpowers the factor two I have from the right.

What could I do to fill the dots? Currently, I just have it without the dots, but I would be happier if I could back it up.

Solution 1:

Assuming $n! \le \left( \frac{n+1}{2} \right)^n$ is true, carry the induction step

$$ (n+1) n!\leq (n+1) \left(\frac{n+1}{2}\right)^n =2 \left(\frac{n+1}{2}\right)^{n+1} \stackrel{?}{\leq} \left(\frac{n+2}{2}\right)^{n+1} $$ But the last inequality is just $$ 2 \le \left( \frac{n+2}{n+1} \right)^{n+1} = \left( 1 + \frac{1}{n+1} \right)^{n+1} $$ It follows because: $$ \left( 1 + \frac{1}{n+1} \right)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} \frac{1}{(n+1)^k} \ge \sum_{k=0}^{1} \binom{n+1}{k} \frac{1}{(n+1)^k} = 1 + (n+1) \frac{1}{n+1} = 2 $$

Solution 2:

Hint:

$$ (n+1)! = (n+1) n! \leq (n+1) \left( \frac{n+1}{2} \right)^n = 2 \left( \frac{n+1}{2} \right)^{n+1}. $$

You can check that $2 \left( \frac{n+1}{2} \right)^{n+1} \leq \left( \frac{n+2}{2} \right)^{n+1}$, by proving that

$$ 2 \leq \left( \frac{n+2}{n+1} \right)^{n+1}. $$

Solution 3:

Hint: $$\left(\frac{n+2}{2}\right)^{n+1}=\frac{n+2}{2}\left(\frac{n+2}{n+1}\right)^n\left(\frac{n+1}{2}\right)^n.$$

Estimate $\left(\frac{n+2}{n+1}\right)^n$.

Solution 4:

$\frac{((n+2)/2)^{n+1}}{((n+1)/2)^{n+1}} = (1 + \frac{1}{n+1})^{n+1} \ge 2$ by the binomial theorem.

Solution 5:

Mine is a tad less elegant but arguably a bit clearer and assumes only the complete basics.

0. The task

Prove that for $ \forall n \in \mathbb{N}$ it is true that $n! \leq (\frac{n+1}{2})^n $ :

I. Base steps

(I need four base steps because my final inequality works for $k \ge 4$.)

$$n=0: 1 \leq (\frac{1}{2})^0 = 1 $$ $$n=1: 1 \leq (\frac{2}{2})^1 = 1 $$ $$n=2: 2 \leq (\frac{3}{2})^2 = \frac{9}{4} $$ $$n=3: 6 \leq (\frac{4}{2})^3 = 8 $$

II. Inductive assumption

$$k! \leq (\frac{k+1}{2})^k$$

III. Inductive hypothesis

$$k! \leq (\frac{k+1}{2})^k \implies (k+1)! \leq (\frac{k+2}{2})^{k+1}$$

IV. Proof

I am going from the assumption to the hypothesis. We will be using the fact that $(a \leq c) \land (b \geq c) \implies a \leq b$.

Step 1.

\begin{align} k! \leq (\frac{k+1}{2})^k && \text{multiply both sides by (k+1)} \tag 1\\ (k+1) k! \leq (k+1) (\frac{k+1}{2})^k && \tag 2\\ (k+1)! \leq (k+1) (\frac{k+1}{2})^k && \text{from the definition of the factorial} \tag 3\\ (k+1)! \leq 2(\frac{k+1}{2}) (\frac{k+1}{2})^k && \text{factoring 2 out of (k+1)} \tag 4\\ (k+1)! \leq 2(\frac{k+1}{2})^{k+1} && \tag 5\\ \end{align}

We have shown that (5) is true. Now, we need to show that $2(\frac{k+1}{2})^{k+1} \leq (\frac{k+2}{2})^{k+1}$, so we prove the initial inequality.

Step 2. \begin{align} 2(\frac{k+1}{2})^{k+1} \leq (\frac{k+2}{2})^{k+1} && \tag 6\\ \end{align}

$$\begin{equation}\begin{aligned} (\frac{k+2}{2})^{k+1} &= (\frac{k+2}{2}) (\frac{k+2}{2})^k \\ &= (\frac{k+2}{k+1})^k (\frac{k+1}{2})^k (\frac{k+2}{2}) \\ \end{aligned}\end{equation}\tag{7}$$

\begin{align} (\frac{k+1}{2})^k (\frac{k+2}{2}) \geq (\frac{k+1}{2})^{k+1} && \tag 8\\ \end{align}

Using the trick already mentioned above by Andre Nicolas we managed to show that the last two terms of equation (7) are greater than the main part of the left hand side of the inequality (6). That leaves us with having to prove that $2 \leq (\frac{k+2}{k+1})^k$.

Step 3. The last step is to notice that $(\frac{k+2}{k+1})$ is in fact equal to one plus a tiny difference and that the increment would get smaller and smaller with greater values of k. So probably it can be represented as $(1 + \frac{1}{k})^k$. And indeed, $ \lim (\frac{k+2}{k+1}) = e$ so for greater $k$s the value of the expression stays close to ~2.76 which is, in particular, more than 2.

This is where we need our four base steps because $2 \leq (\frac{k+2}{k+1})^k$ holds only for $k \in \mathbb{N}-\{0,1,2,3\} $(at least for $k \geq 0)$. The four test cases get us covered here and allow the induction to work.