Proving $\frac{n^n}{3^n} < n! < \frac{n^n}{2^n}$ holds by induction

Question

I am Computer Science person, and I'm trying to beef up my mathematical skills a little bit. This isn't homework and I don't have a professor I can go to to ask for help. I hope this is an appropriate forum for this type of question.

To learn more about inductive proofs, I am reading the Wikipedia article on them. However, I am having trouble solving one of the examples on the page:

$$P(n) :\quad \frac{n^n}{3^n} < n! < \frac{n^n}{2^n} .$$ Prove $P(n) \; \forall n \in \mathbb{N}, n \ge 6$

Here is what I've done so far, with the "???" indicating where I don't know the next step.

Base case: $$\begin{array}{rrcccl} P(6)\colon& \frac{6^6}{3^6} &<& 6! &<& \frac{6^6}{2^6}\\ \iff& 2^6 &<& 6! &<& 3^6\\ \iff& 64 &<& 720 &<& 729 \end{array}$$

Inductive step:

$$\begin{array}{rrccclc} P(n+1) \colon&\frac{(n+1)^{n+1}}{3^{n+1}} &<& (n+1)! &<& \frac{(n+1)^{n+1}}{2^{n+1}}\\ \iff& \frac{(n+1)^{n+1}}{3^{n+1}} &<& (n+1)n! &<& \frac{(n+1)^{n+1}}{2^{n+1}} &\text{Defn factorial}\\ \iff& \frac{(n+1)(n+1)^n}{3 \cdot 3^n} &<& (n+1)n! &<& \frac{(n+1)(n+1)^n}{2 \cdot 2^n} &\{a^{m+n} = a^m a^n\}\\ \iff& \frac{(n+1)^n}{3 \cdot 3^n} &<& n! &<& \frac{(n+1)^n}{2 \cdot 2^n} &\text{Divide by n+1}\\ ??? \end{array}$$

Perhaps this just looks hopelessly foolish from the point of view of mathematicians, but I'm trying to learn.

Specifically what I am looking for is either guidance to arrive at the answer on my own, or pointers to documentation I should read to further my own understanding.

Answer 1

As a matter of style, I would start with $P(n)$, and from there try to prove $P(n+1)$. This makes it slightly less tricky to correctly manipulate inequalities.

So if we have $$\frac{n^n}{3^n} < n! < \frac{n^n}{2^n},$$ how do we get $P(n+1)$? Multiplying through by $n+1$ was a good instinct: $$\frac{(n+1)n^n}{3^n} < (n+1)! < \frac{(n+1)n^n}{2^n}.$$ There are now two pieces we need to prove: $$\frac{(n+1)^{n+1}}{3^{n+1}} < \frac{(n+1)n^n}{3^n}$$ and $$\frac{(n+1)n^n}{2^{n}} < \frac{(n+1)^{n+1}}{2^{n+1}}.$$

Here's a hint for these two inequalities: $\left(1+\frac{1}{n}\right)^n$ is an increasing function (prove this) that's bounded below by $2$ (when $n=1$) and converges to $e$. Let me know if you want something more explicit.

Answer 2

For the Inductive Step:

Suppose that we have

$$ \frac{n^n}{3^n} < n! $$ and $$ n! < \frac{n^n}{2^n}. $$

We want to show that this implies that

$$ \frac{(n+1)^{n+1}}{3^{n+1}} < (n+1)! $$ and $$ (n+1)! < \frac{(n+1)^{n+1}}{2^{n+1}}. $$

Under these assumptions, to see the first inequality holds, write: $$\begin{align} \frac{(n+1)^{n+1}}{3^{n+1}} &= \frac{(n+1)}{3} \frac{(n+1)^n}{3^n} \\ &= \frac{n+1}{3} \left(\frac{n+1}{n}\right)^n \frac{n^n}{3^n} \\ &< \frac{n+1}{3} \left(\frac{n+1}{n}\right)^n n! \qquad (\text{using inductive hypothesis}) \\ &= \left( 1 + \frac{1}{n} \right)^n \frac{1}{3} (n+1)! \end{align}$$ and this reduces to showing that $$ \left( 1 + \frac{1}{n} \right)^n \frac{1}{3} < 1. $$ The other inequality can be handled similarly. You can probably save some paper by doing both inequalities at the same time, but if you are just starting out, I would suggest working with one inequality at a time.

Answer 3

You have two inequalities to prove. You should prove them separately. There may be some duplication in typing, but the gain in logical clarity will be worth it.

Let $P(n)$ be the assertion that $n!<\frac{n^n}{3^n}$. We want to show that $P(n)$ holds for $n \ge 6$.

A minor computation deals with the base case $n=6$. Now I would like to show that if $P(n)$ holds when $n=k$, where $k$ is an integer $\ge 6$, then $P(n)$ holds when $n=k+1$. Unfortunately, you have chosen an example where this "induction step" is less easy than in many other cases.

So we assume that we know that $k! <\dfrac{k^k}{2^k}$. We want to show that $(k+1)!< \dfrac{(k+1)^{k+1}}{2^{k+1}}.$

How shall we exploit our knowledge about $k!$ to gain information about $(k+1)!$? It seems clear that we should try to exploit the relationship between $k!$ and $(k+1)!$. Since $(k+1)!=k!(k+1)$, and we know that $k! < \frac{k^k}{2^k}$, we have $$(k+1)!<(k+1)\frac{k^k}{2^k}.$$ If we could show that $(k+1)\dfrac{k^k}{2^k} <\dfrac{(k+1)^{k+1}}{2^{k+1}}$, we would be finished. A little algebra shows that "all" we need to do is to show that $k^k<\dfrac{(k+1)^k}{2}$, or equivalently that $\frac{(k+1)^k}{k^k}>2$. Rewrite this as the more familiar $\left(1+\frac{1}{k}\right)^k>2$.

Calculator experimentation seems to show that the required inequality is indeed true for all $k>1$. But we need to prove it, at least for $k \ge 6$. Induction anyone? We will use another tool.

Recall that by the Binomial Theorem, $$(1+x)^k =1+\binom{k}{1}x+\binom{k}{2}x^2 +\binom{k}{3}x^3+ \cdots +\binom{k}{k}x^k.$$ Put $x=\frac{1}{k}$. The first two terms in the binomial expansion of $\left(1+\frac{1}{k}\right)^k$ are $1$ and $k(1/k)$. They already add up to $2$. If $k>1$, the remaining terms put us above $2$. This finishes the proof.

An argument along similar lines shows that the other inequality also holds. We end up needing to show that $\left(1+\frac{1}{k}\right)^k <3$, which is somewhat harder than showing that $\left(1+\frac{1}{k}\right)^k >2$. There are a number of ways to handle that inequality. One way is to prove (by induction) that $\left(1+\frac{1}{k}\right)^k <3-\frac{1}{k}$. Strangely enough, this turns out to be easier to prove than the weaker inequality $\left(1+\frac{1}{k}\right)^k <3$.

Comment: Please note that the fact that you could not push the argument through does not mean that you don't know what induction is about. In your problem, the proof of the required inequalities is not obvious. You might try your hand at easier standard examples, such as the fact that $1^2+2^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6}$.