13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is tangential to the question, but it's very useful to know that $(n/3)^n \leq n! \leq (n/2)^n$ for all sufficiently large $n$. This is an extremely rough version of Stirling's formula, and in many applications it is all one needs. The inequalities can be derived by taking $k=2,3$ in applying the ratio test to the series $\sum_n (n/k)^n/n!$ (recall that $e = \lim_n (1 + 1/n)^n$). The same argument shows that $n! \geq (n/k)^n$ eventually holds if $k > e$, and the reverse eventually holds if $0 < k < e$. Seeing how $n!$ compares to $(n/e)^n$ is of course Stirling's formula territory. $\endgroup$ – leslie townes Oct 26 '11 at 22:13
  • $\begingroup$ See also: math.stackexchange.com/questions/523529/… and math.stackexchange.com/questions/992056/… $\endgroup$ – Martin Sleziak Oct 19 '15 at 5:00
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very cool, thanks a lot for breaking it down so much! $\endgroup$ – Martin Ueding Oct 26 '11 at 19:12
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Maybe I do not look right, but isn't that what I have above just in reverse? $\endgroup$ – Martin Ueding Oct 26 '11 at 19:00
  • $\begingroup$ I did just rewrite what you have to a certain extent. That's fair. But now it's clear exactly what you have to to fill in the gaps. $\endgroup$ – JavaMan Oct 26 '11 at 19:01
  • $\begingroup$ I was just too fast, now it helps. Thanks! $\endgroup$ – Martin Ueding Oct 26 '11 at 19:12
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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