Find the smallest k such that $n^k > \sum_{i=0}^{n-1} i^k$

Note: This post contains only numerics; see the answers by robjohn and Jack D'Aurizio for actual math.

Numerical computations show that $$k(n) = \lfloor n\log 2-0.039721\rfloor \quad \text{ for } \ 2\le n<944029$$ which is kind of nice. However, this empirical formula breaks down for $n=944029$. What is worse, it turns out there is no $c$ such that $k(n) = \lfloor n\log 2-c\rfloor$ holds for all $n$. Indeed, we have $$k(944029) = 654351, \quad \text{with } 944029\log(2)-654351 < 0.039717$$ $$k(603162) = 418079, \quad \text{with } \ 603162 \log 2 - 418079 > 1.0397208$$ So, the range of values of $n\log 2-k(n)$ exceeds $1$, if only by a tiny bit.

Still, it is reasonable to conjecture that $$\lfloor n\log 2\rfloor-1 \le k(n) \le \lfloor n\log 2\rfloor \tag{??}$$ for all $n\ge 2$.

The upper bound was proved by Jack D'Aurizio and by robjohn; also, robjohn gave a lower bound that is very close to (??).

Using the inequality $$ e^{-x/(1-x/k)}\le\left(1-\frac xk\right)^k\le e^{-x}\tag{1} $$ and setting $x=\frac{ik}{n}$ we get $$ \begin{align} \frac1{n^k}\sum_{i=0}^{n-1}i^k &=\frac1{n^k}\sum_{i=1}^n(n-i)^k\\ &=\sum_{i=1}^n\left(1-\frac in\right)^k\\ &\le\sum_{i=1}^ne^{-ik/n}\\ &\le\frac1{e^{k/n}-1}\tag{2} \end{align} $$ Thus, $k=\log(2)n$ is an upper bound.

Assuming $k/n$ is near $\log(2)$, we have for any $\alpha\gt0$, $$ \begin{align} \hspace{-1cm}\frac1{n^k}\sum_{i=0}^{n-1}i^k &=\frac1{n^k}\sum_{i=1}^n(n-i)^k\\ &=\sum_{i=1}^n\left(1-\frac in\right)^k\\ &\ge\sum_{i=1}^ne^{-ik/(n-i)}\\ &=\sum_{i=1}^ne^{-ik/n}-\sum_{i=1}^ne^{-ik/n}\left(1-e^{-i^2k/n/(n-i)}\right)\\ &\ge\color{#00A000}{\sum_{i=1}^ne^{-ik/n}}\color{#C00000}{-\sum_{i=1}^ne^{-ik/n}\frac{i^2k}{n(n-i)}}\\ &\ge\color{#00A000}{\sum_{i=1}^\infty e^{-ik/n}}\color{#C00000}{-\frac1{1-\alpha}\sum_{i=1}^{\alpha n}e^{-ik/n}\frac{i^2k}{n^2}-\sum_{i=\alpha n+1}^ne^{-ik/n}\frac{i^2k}{n}}\color{#00A000}{-\sum_{i=n+1}^\infty e^{-ik/n}}\\ &\ge\frac1{e^{k/n}-1}-\frac1{1-\alpha}\frac{k}{n^2}\frac{e^{-k/n}+e^{-2k/n}}{(1-e^{-k/n})^3}\color{#0000FF}{-e^{-\alpha k}\frac{nk}{e^{k/n}-1}-\frac{e^{-n}}{e^{k/n}-1}}\\ &\sim\frac1{e^{k/n}-1}-\frac{6\log(2)}{(1-\alpha)n}\tag{3} \end{align} $$ because the blue terms decay exponentially.

Since the derivative of $\frac1{e^x-1}$ at $x=\log(2)$ is $-2$, we get $\frac1{e^{k/n}-1}-\frac{6\log(2)}{n}=1$ at approximately $k=\log(2)(n-3)$. With a bit more care, we see that more precisely: $$ k=\log(2)(n-3)-\frac{3\log(2)(17\log(2)-6)}{2n}+\dots\tag{4} $$ Therefore, $k=\log(2)(n-3)$ is a good estimate for the lower bound.

Proof of the Inequality

Since $1+x\le e^x$ for $x\in\mathbb{R}$, we have $$ 1-\frac xk\le e^{-x/k}\le\frac1{1+\frac xk}=1-\frac{x}{k+x}\tag{5} $$ Therefore, $$ e^{-x/(k-x)}\le1-\frac xk\le e^{-x/k}\tag{6} $$ Raising to the $k^\text{th}$ power, $$ e^{-x/(1-x/k)}\le\left(1-\frac xk\right)^k\le e^{-x}\tag{7} $$ as desired.