# Show that $(\frac{n}{3})^{n}<n! < (\frac{n}{2})^{n}$

$$(\frac{n}{3})^{n}

My appraoch so far

Idon't know for which inductionbase this formula would applyso I have startedwith the inductionstep:

$$(n+1)! = (n+1)n! > (n+1)(\frac{n}{3})^{n} = n^{n}(\frac{1}{3})^{n}(n+1)$$

$$(\frac{n+1}{3})^{n+1}= (\frac{n+1}{3})^{n}(\frac{n+1}{3})=(\frac{1}{3})^{n}(n+1)(\frac{(n+1)^n}{3})$$

Only thing left to show would be $$n^n \geq (\frac{(n+1)^n}{3})$$

But I am not sure if I haven't done a mistake yet and hoq to prove this last inequality. Note that this excercise is from a chapter where biniommialcoefficients werenot introduced yet.

I also need to find the introductionbase and proof the other side of the inequality, is it possible to use the bernoulliinequality somewhere?

We need to know that $$2\le\left(\frac{n+1}{n}\right)^n for all $$n\ge1$$.

So, if $$n!<(n/3)^n$$, then $$(n+1)!<(n+1)\frac{n^n}{3^n}<(n+1)\frac{n^n}{3^{n+1}}\left(\frac{n+1}{n}\right)^n=\left(\frac{n+1}3\right)^{n+1}.$$ The other inequality is similar.

• I have got problems to proof the right inequalityof your prerequisite, I have already made a question about it. If you know how I can proofit using basic induction I wouldbe glad if you couldgive me an answer to it. My approach so far : $b_n - b_{n+1} > 0 \rightarrow b_n > b_{n+1}\iff (1+\frac{1}{n})^{n+1}- (1+\frac{1}{1+n})^{n+2} > 0 \rightarrow (1+\frac{1}{n})^{n+1} > (1+\frac{1}{1+n})^{n+2}$ – RM777 Nov 7 '18 at 21:54
• If the previous statementsare truethan by induction one can show that [so based on that $(1+\frac{1}{n})^n < 3$ is true] $(1+\frac{1}{n+1})^{n+1}< (1+\frac{1}{n+1})^{n+2} < (1+\frac{1}{n})^{n+1}= (1+\frac{1}{n})(1+\frac{1}{n})^n < (1+\frac{1}{n})3 \rightarrow (1+\frac{1}{n+1})^{n+2} < (1+\frac{1}{n})3 \iff (1+\frac{1}{n+1})(1+\frac{1}{n+1})^{n+1} < (1+\frac{1}{n})3 \iff (1+\frac{1}{n+1})^{n+1} < \frac{1+\frac{1}{n}}{1+\frac{1}{n+1}}3$ – RM777 Nov 7 '18 at 21:57
• Unfortunately the nominateris bigger than the denominater inthe last term so the estimate is not sufficient. – RM777 Nov 7 '18 at 22:00

Let us show that $$a_n=\left(1+\frac{1}{n}\right)^n$$ for $$n\geq 1$$ gives an increasing sequence bounded by $$3$$.

Increasing. The product of $$k$$ positive numbers can always be written as the $$k$$-th power of their geometric mean. In particular $$1\cdot\left(1+\frac{1}{n}\right)^n = \text{GM}\big(1,\underbrace{1+\tfrac{1}{n}}_{n\text{ times}}\big)^{n+1}\color{red}{<}\text{AM}\big(1,\underbrace{1+\tfrac{1}{n}}_{n\text{ times}}\big)^{n+1}=\left[\frac{1+n\left(1+\tfrac{1}{n}\right)}{n+1}\right]^{n+1}$$ by the AM-GM inequality. If we expand the RHS, we exactly get $$a_n.

Bounded by $$3$$. By the binomial theorem and the fact that $$\binom{n}{k}\leq\frac{n^k}{k!}$$ we have: $$\left(1+\frac{1}{n}\right)^n = 1+\sum_{k=1}^{n}\binom{n}{k}\frac{1}{n^k}\leq 1+\sum_{k=1}^{n}\frac{1}{k!}$$ for any $$n\geq 1$$, hence $$a_n$$ is bounded by $$1+\sum_{k\geq 1}\frac{1}{k!}$$.
On the other hand, for any $$k\geq 3$$ we have $$k!\geq 2\cdot 3^{k-2}$$, hence $$a_n \leq 1+1+\frac{1}{2}+\sum_{k\geq 3}\frac{1}{2\cdot 3^{k-2}}=\frac{11}{4}\color{red}{<3}.$$

Since any increasing and bounded sequence is convergent to its supremum, this shows that $$\lim_{n\to +\infty}\left(1+\frac{1}{n}\right)^n$$ is a mathematical constant less than three, and with few efforts you may also prove that such mathematical constant is exactly $$\sum_{k\geq 0}\frac{1}{k!}$$ a better-suited representation for numerical purposes, since such series is rapidly convergent. $$\left(\sum_{k\geq 0}\frac{1}{2^k k!}\right)^2$$ or $$\left(\sum_{k\geq 0}\frac{(-1)^k}{k!}\right)^{-1}$$ are even better.

Relations with the factorial. By defining $$b_n$$ as $$\frac{n^n}{n!}$$ we have $$b_1=1$$ and $$\frac{b_{n+1}}{b_n} = \frac{(n+1)^{n+1}}{(n+1)!}\cdot\frac{n!}{n^n}=\left(1+\frac{1}{n}\right)^n,$$ hence $$b_{n+1}=b_1\prod_{k=1}^{n}\frac{b_{k+1}}{b_k}=\prod_{k=1}^{n}\left(1+\frac{1}{k}\right)^k \in (2^n,3^n).$$ This gives a weak version of Stirling's inequality,

$$\frac{(n+1)^{n}}{3^n}

It seems to me that this inequality is wrong.

This is the plot of the three functions

And here a numerical example

$$(\frac{5}{3})^5 = 12.86008$$

$$5!=120$$

$$(\frac{5}{2})^5 = 97.65625$$

It may be valid for some n or even for n > m but at least it is not valid for any n.

• The original task was also to rather find theinduction base and not to do the induction. However once you have found an n for which the inequality holds you know that it will also hold for the successor. – RM777 Nov 7 '18 at 22:04
• True, though the question is incomplete, isn't it? – Francesco Iovine Nov 8 '18 at 5:22

Since a sequence $$a_n =(1+n^{-1})^n$$ is increasing and its limit is equal $$e<3$$ we get $$(1+n^{-1})^n <3$$ for all $$n\in \mathbb{N}$$

• Try taking logarithm and use stirling's approximation of n! You will get a strict inequality. Even you can start with $3^{-n }< e^{-n}< 2^{-n}$ – NewBornMATH Nov 6 '18 at 18:23
• @NewBornMATH: How can you assume that Stirling's inequality is allowed when Euler's constant still has to be defined, reasonably? – Jack D'Aurizio Nov 6 '18 at 18:42
• @Jack D' Aurizio sorry sir i did not get what you are saying i guess Stirling's inequality can be proved without euler's constant. math.stackexchange.com/questions/94722/stirlings-formula-proof – NewBornMATH Nov 7 '18 at 13:38
• @NewBornMATH: if you write down Stirling's inequality/approximation, you'll see there is an $e=\lim_{n\to +\infty}\left(1+\frac{1}{n}\right)^n$ in it. – Jack D'Aurizio Nov 7 '18 at 13:48
• @Jack D'Aurizio ohh ! Yes you are right i got it. I initially thought that you are talking about euler mascheroni constant.Apologies. – NewBornMATH Nov 7 '18 at 15:13