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

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]