# Why $e^kn^k<k^ke^{\frac {n-k}{2^k}}$ whenever $n \geq k^2 2^k \ln 2 (1+o(1))$?

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.

EDIT

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.

• 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. – 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.

• 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?) – Emolga May 4 '17 at 13:09