Let $k$ be a natural number. I want to find a "good" (low) value of $n(k)$ which satisfies $e^kn^k<k^ke^{\frac {n-k}{2^k}}$.

I read that an answer is $n \geq k^2 2^k \ln 2 (1+o(1)) $, where the little o is as a function of $k$. Heuristically this is since the $2^k$ cancel and we are left with $\approx e^{k^2}$ which is larger than the term $n^k \approx k^{2k} 2^{k^2}$.

How do I show this more rigorously? And why is the $\ln2$ necessary?

If we write $n=k+2^kk^2\ln 2$ (which is of the requested form), we are left with showing that $e^k (k+2^k k^2\ln2)^k \leq k^k2^{k^2}$ for all $k$, which seems false since the LHS is at least $2^{k^2}(k^2 \ln2)^k$, so this easy choice of the $o(1)$ term does not work.


User Clement C. explained (thanks) that the heuristic explanation for the optimality of the constant $\ln 2$ (which makes $n$ smaller) is that this translates the base in the dominant term $e^{k^2}$ to $2^{k^2}$, same as the left hand side.

  • 1
    $\begingroup$ The $\ln 2$ will come from the fact that there is a $2^k = e^{k\ln 2}$ in the inequality you want to establish. $\endgroup$ – Clement C. May 1 '17 at 13:41

$e^kn^k<k^ke^{\frac {n-k}{2^k}}$ is equivalent to $en<ke^{\frac {n/k-1}{2^k}} $ or $\ln n+1 \lt \ln k+\frac {n/k-1}{2^k} $.

Let $m = n/k$. This becomes $\ln m+\ln k+1 \lt \ln k+\frac {m-1}{2^k} $ or $\ln m+1 \lt \frac {m-1}{2^k} $.

Let $r = 2^k$. This now is $\ln m+1 \lt \frac {m-1}{r} $ or $r \le \frac{m-1}{\ln m +1} $.

The right side looks like $\frac{m}{\ln m}$, and it is known that the solution to $x =\frac{m}{\ln m}$ is about $m = x\ln x $.

Let's look at $r = \frac{m-1}{\ln m +1} $ or $m =r(\ln m +1)+1 $. I'll treat this as an iteration for $m$.

Let $m_0 =r \ln r $. Then

$\begin{array}\\ m_1 &=r(\ln m_0 +1)+1\\ &=r(\ln (r \ln r) +1)+1\\ &=r(\ln r+\ln \ln r +1)+1\\ &\approx r(\ln r+\ln \ln r +1)\\ &= m_2\\ \end{array} $

Writing this in terms of $n$ and $k$, $m = n/k$ and $r = 2^k$ so $n/k \approx 2^k(k\ln 2+\ln(k \ln 2) +1) $ or

$\begin{array}\\ n &\approx k2^k(k\ln 2+\ln k +\ln\ln 2 +1)\\ &= k^22^k\ln 2(1+\frac{\ln k +\ln\ln 2 +1}{k \ln 2})\\ &= k^22^k\ln 2(1+\frac{\ln k}{k \ln 2}+O(\frac1{k}))\\ \end{array} $

As to the error in this, I don't feel like grinding through any more.

  • $\begingroup$ Thank you for taking the time to answer. I cannot produce a rigorous proof of the claim from it, though. This answer provides the leading term of the unknown $o(1)$ term using some methods that look heuristics to me; is the iteration a formal proof or an indication of what should be the term? Is formally proving such a thing considered "not interesting"? (How can I be sure of the argument's correctness, then?) $\endgroup$ – Emolga May 4 '17 at 13:09

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.