Sum of powers-of-integers bound 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.$
 A: 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}
$$
A: 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.
A: 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<n^{n+1}
$$
Dividing by $n+1$, we get
$$
\begin{align}
\sum_{k=0}^{n-1}k^n
&<\frac{1}{n+1}n^{n+1}\\
&<n^n
\end{align}
$$
A: 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. 
