7
$\begingroup$

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.$

4 Answers 4

9

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} $

  • 0
    Thanks mjqxxxx for this nice proof. I was ne$v$er very good $a$t using integrals to $b$ound sums -- signs of $a$ mis-spent youth, perhaps.2011-12-16
6

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.

  • 0
    @Derek: That is funny. Small world, huh? :)2011-12-16
4

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 Dividing by $n+1$, we get $ \begin{align} \sum_{k=0}^{n-1}k^n &<\frac{1}{n+1}n^{n+1}\\ &

  • 0
    Thanks robjohn. Applying the last expression to the example above gives 1^4 + 2^4 + 3^4 = 1+16+81 = 98 < 4^5/5 = 204.8 < 4^4 = 256. Interesting.2011-12-16
3

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.

  • 0
    Thanks Srivatsan. Your proof and the others above will keep me busy for a few days. It's great having different proofs for the same problem.2011-12-16