I am looking for a nice proof of this inequality: \begin{equation} \sum_{k=1}^{n-1} k^n < n^n, \quad n > 0. \end{equation}
Example: $1^4 + 2^4 + 3^4 = 1+16+81 = 98 < 4^4 = 256.$
I am looking for a nice proof of this inequality: \begin{equation} \sum_{k=1}^{n-1} k^n < n^n, \quad n > 0. \end{equation}
Example: $1^4 + 2^4 + 3^4 = 1+16+81 = 98 < 4^4 = 256.$
Bounding the sum by the corresponding integral: $$ \begin{eqnarray} \sum_{k=1}^{n-1} k^n &=& n^{n+1}\sum_{k=0}^{n-1}\left(\frac{k}{n}\right)^{n}\frac{1}{n} \\ &\le& n^{n+1}\int_{0}^{1}x^n dx \\ &=& n^{n+1} \frac{x^{n+1}}{n+1}\Bigg\vert_{0}^{1} \\ &=& \frac{n^{n+1}}{n+1} \\ &<& n^n. \end{eqnarray} $$
I wrote an expository paper on this inequality several years ago. It contains outlines of two proofs of it. One is the proof by mjqxxxx; the other is as follows.
By the binomial theorem, we know that, if $0 \leq k < n$, $$(k+1)^n = \sum_{j=0}^n \binom{n}{j} k^j > k^n + nk^{n-1} \geq 2k^n,$$ which implies that $(k+1)^n - k^n > k^n$ for $0 \leq k \leq n$.
Thus, $$\sum_{k=0}^{n-1} k^n < \sum_{k=0}^{n-1} \left((k+1)^n - k^n\right) = n^n.$$
The main point of the paper, though, was to investigate how much less, in the limit, the left-hand side is than the right-hand side. Specifically, the paper shows that $$\lim_{n \to \infty}\sum_{k=0}^{n-1} \left(\frac{k}{n}\right)^n = \frac{1}{e-1}. \tag{1}$$ Thus, in the limit, the sum $\sum \limits_{k=0}^{n-1} k^n$ represents $\frac{1}{e-1} \approx 0.582$ of the single term $n^n$.
The paper was "The Euler-Maclaurin Formula and Sums of Powers," Mathematics Magazine, 79 (1): 61-65, 2006. Here's a near-final draft of the paper. There's actually a subtle error in it that was pointed out by someone else a few years later; see my letter to the editor correcting the error and generalizing the result to $$\lim_{n \to \infty}\sum_{k=0}^{n+m} \left(\frac{k}{n}\right)^n = \frac{e^{m+1}}{e-1}. \tag{2}$$
There have been a couple of follow-up papers by others, too. Finbarr Holland published two additional derivations of the limiting result (1), and Vito Lampret showed that the sum in (2) with $m = 0$ is increasing in $n$ to $\frac{e}{e-1}$ and gave an estimate of its rate of convergence.
The Mean Value Theorem says that for some $\xi$ between $k$ and $k+1$,
$$
(k+1)^{n+1}-k^{n+1}=(n+1)\xi^n>(n+1)k^n
$$
Therefore, by telescoping series,
$$
\sum_{k=0}^{n-1}(n+1)k^n
For all $0 \leqslant r \leqslant n-1$, we have $$ \frac{(r+1)^n}{r^n} = \left( \frac{r+1}{r} \right)^n = \left( 1 + \frac{1}{r} \right)^n \geqslant 1 + \frac{n}{r} \geqslant 2, $$ so $r^n \leqslant \frac{1}{2} (r+1)^n$. Now by a simple induction on $k$, we obtain $$ (n-k)^n \leqslant \frac{n^n}{2^k}. $$ Summing over $k = 1, 2, \ldots, n-1$, we get $$ \sum_{k=1}^{n-1} (n-k)^n \leqslant n^n \sum_{k=1}^{n-1} 2^{-k} < n^n \sum_{k=1}^{\infty} 2^{-k} = n^n, $$ which is what we wanted to show.
This approach can squeeze out a little more. In the very first step, assuming $\varepsilon > 0$ and $n$ sufficiently large, we have $$ \frac{(r+1)^n}{r^n} = \left( 1 + \frac{1}{r} \right)^n \geqslant \left( 1 + \frac{1}{n} \right)^n \geqslant \mathrm e - \varepsilon. $$ Plugging in this refined bound in the above proof, we get the upper bound $$ \sum_{k=1}^{n-1} k^n \lt n^n \cdot \sum_{k=1}^{\infty} (\mathrm{e} - \varepsilon)^{-k} = \frac{n^n}{\mathrm e - \varepsilon - 1}. $$ This gives $$ \limsup_n \ n^{-n} \cdot \sum_{k=1}^{n-1} k^n \leqslant \frac{1}{\mathrm e - 1}, $$ that matches (one half of) the limit obtained by Mike Spivey.