**POLYA008: First n for which m^n < n! **(proposed by Floor
van Lamoen, 11/15/01).

Suppose that N_m denotes the first n for which m^n < n! Can we say something about the value of N_{m+1} knowing the value of N_m?

Background: I got fascinated by this problem when I was just calculating
for fun some of the N_m values. I was struck by the fact that these values
only gave N_{m+1} is either N_m + 2 or N_m + 3. I entered the N_m's
and the differences in Neil Sloane's *Encyclopedia of Integer Sequences:*

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A065027

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A065067

**Discussion. [SCL, 11/15/01]: **This is only a rough
guess, but perhaps this is related to the fact that ((m+1)/m)^m is approximately
e. This seems a likely reason but I haven't started thinking about details.
If N_m is appromimately c*m, then ((m+1)/m)^{N_m} should be about e^c,
and (m+1)^{N_m} ~ e^c*m^{N_m} <e^c*(N_m)! ....?

**[FvL, 11/15/01]: **My own though was using the approximation
of (n!)^(1/n) by (2n\pi)^(1/2n) * n/e ~ n/e. This approximation might be
good enough to show that indeed N_{m+1} is either N_m + 2 or N_m + 3.

**[TS, 12/27/01]: A postscript
file of the following is also available.**

\documentclass{article}

\begin{document}

\noindent\textbf{Discussion/Solution.} I prove,
rigorously I hope, that \textit{if $m$ is large enough}, then $N_{m+1}
\in \{N_m+2 ,N_m+3\}$, where the integer $N_m$ is defined to be the first
integer $n$ for which $m^n<n!$. It is also easy to decide what ``large
enough'' means; i.e., how large $m$ should be. I believe the estimates
hold already for $m\ge 18$; since the cases in which $m\le 17$ can be verified
by direct computation, the result would hold for all positive integers
$m$. We use the following version of Stirling's formula (cf \cite{WW}[12.5]):

\[

\Gamma(t) = e^{-t}t^{t-1/2}\sqrt{2\pi}e^{\theta(t)/t}

\]

valid for all $t>0$ where $\theta:(0,\infty)\to [0,\frac
1{12}]$. Let $m$ be a positive integer and let $n = N_m$ so that $m^n<n!$
while $m^{n-1} \ge (n-1)!$ (the only case in which we can have equality
is $m=1$). We begin with $m^n < n! = n\Gamma(n)$, use Stirling's formula
for $t=n$ to evaluate the right hand side, and take the $n$-th root of
both sides to get

\begin{equation}

\label{e1}

m < e^{-1}n\left(2\pi n\right)^{1/2n}e^{\theta(n)/n^2}

\end{equation}

Writing $(n+3)! = (n+3)\Gamma(n+3)$, using Stirling's
formula for $t = n+3$, and taking the $n+3$-rd root, we see that

\begin{eqnarray*}

(n+3)!^{1/(n+3)} &=&

e^{-1}(n+3)(2\pi(n+3))^{1/(2(n+3)}e^{\theta(n+3)/(n+3)^2}\\

&\ge& e^{-1}(n+3)(2\pi(n+3))^{1/(2(n+3)}.

\end{eqnarray*}

Let $x = \log(2\pi(n+3))/(2(n+3))$ so that

\[

(2\pi(n+3))^{1/(2(n+3)} = e^x > 1+x

= 1 + \frac{\log(2\pi(n+3))}{2(n+3)},

\]

hence

\begin{equation}

(n+3)!^{1/(n+3)} > \frac{n+3}e + \frac{\log[2\pi(n+3)]}{2e}.

\label{e2}

\end{equation}

From (\ref{e1}) and the fact that $\theta(t)\le 12$ for
all $t>0$,

\[

m < e^{-1}n\left(2\pi n\right)^{1/2n}e^{12/n^2} =
\frac n e e^z

\]

where $z = (1/2n)\log(2\pi n)+(12/n^2)$. By Taylor's
formula,

\begin{eqnarray*}

m &<& \frac ne\left(1 + z + \frac 12 z^2 e^z\right)
= \frac n e + \frac{\log(2\pi n)}{2e} + \frac {12}{ne} +

\frac 12 nz^2e^{z-1}\\

&=& \frac n e + \frac{\log(2\pi n)}{2e} + \frac
{12}{ne} + O(\frac{\log^2 n}n)

= \frac n e + \frac{\log(2\pi n)}{2e} + O(\frac{\log^2
n}n)

\end{eqnarray*}

Subtracting from (\ref{e2}) we get

\[

(n+3)!^{1/(n+3)} - m > \frac 3 e +\frac {\log(\frac{n+3}n)}{2e}
-O(\frac{log n}n) > \frac 3 e -O(\frac{log n}n).

\]

Since $3/e>1$, and since clearly $n = N_m >m$, it follows
that for $m$ large enough we have

\[

(n+3)!^{1/(n+3)} - m > 1; \, \mbox{ i.e., }\,

(n+3)! > (m+1)^{n+3}.

\]

This proves that $N_{m+1}\le N_m+3$ if $m$ is large enough.
In trying to determine how large is ``large enough,'' we can be more careful
in estimating the term that appears as $O(\log^2 n/n)$. I get that for
$n = 45$ (which roughly corresponds to $m = 18$) the term is $<0.1$.
Because $(3/e)-1 > 0.1$, this would prove that $N_{m+1}\le N_m+3$ for $m\ge
18$, and it is easily verified to hold by direct computations for $m\le
17$. The proof that $N_{m+1}\ge N_m+2$ is similar. From

\[

m^{n-1}>(n-1)! = (n-1)\Gamma(n-1)

\]

we get applying Stirling's formula with $t = n-1$ and
taking the $(n-1)$-st root,

\begin{eqnarray}

\label{e3}

m &>& e^{-1}(n-1)(2\pi(n-1))^{1/2(n-1)}e^{\theta(n-1)/(n-1)^2}\\

&\ge&

e^{-1}(n-1)(2\pi(n-1))^{1/2(n-1)}.\nonumber

\end{eqnarray}

By Stirling, with $t = n+1$ applied to $(n+1)! = (n+1)\Gamma(n+1)$,
after taking the (n-1)-st root, we get

\begin{eqnarray*}

(n+1)!^{1/(n+1)} &=&

e^{-1}(n+1)(2\pi(n+1))^{1/2(n+1)}e^{\theta(n+1)/(n+1)^2}\\

&\le &

e^{-1}(n+1)(2\pi(n+1))^{1/2(n+1)}e^{12/(n+1)^2}.

\end{eqnarray*}

Subtracting from (\ref{e3}), and proceeding very much
as we did before to prove $N_{M+1}\le N_m+3$, we get

\[

m-(n+1)!^{1/(n+1)} > \frac{n-1}e-\frac{n+1}e - O(\frac{\log^2
n}n)

= -\frac 2e - O(\frac{\log^2 n}n).

\]

Since $2/e<1$, we proved that

\[

m+1>(n+1)!^{1/(n+1)}; \,\mbox{ i.e. }\, (m+1)^{n+1}>(n+1)!,

\]

hence $N_{m+1}>n+1 =N_m+1$, if $m$ is large enough. Once
more, it is easy to estimate how large $m$ has to be so that it is ``large
enough,'' and one can deal with the smaller cases by direct computation.

\begin{thebibliography}{99}

\bibitem{WW} E.T. Whittaker and G.N. Watson, \textit{Modern

Analysis}, Cambridge University Press, Cambridge 1952.

\end{thebibliography}

\end{document}

**Bibliography.**
**Return to [Polya
Home Page] [Members]
[Problem Center]
[Inventory]
[Reserve Area]**