How to prove "For every positive integer n, $1^{n}$ + $2^{n}$ + ... + $n^{n}$ < $(n+1)^{n}$." by using induction?

Question

How can I prove the following theorem:

For every positive integer $n$, $1^n + 2^n + ... + n^n \lt (n+1)^n$

by using induction?

I have proved that "for every real number $x > 0$ and every non-negative integer $n$, $x^{n} + n \cdot x^{n-1} \le (x+1)^n$". It might be useful. Thank you.

Answer 1

Let me try. Assuming that you have $$(P) \ \ \ \ \sum_{i=1}^k i^k < (k+1)^k$$. Now we prove that $$\sum_{i=1}^{k+1} i^{k+1} < (k+2)^{k+1}$$.

We have $$LHS = \sum_{i=1}^{k+1} i^{k+1} < (k+2)\sum_{i=1}^k i^k + (k+1)^{k+1} < (k+2)(k+1)^{k} + (k+1)^{k+1}< (k+2)^{k+1}.$$ (using your inequality with $x= k+1$)

Answer 2

Not your question, but you can do it directly:

\begin{align}(n+1)^n&=n^n+\binom{n}{n-1}n^{n-1}+\binom{n}{n-2}n^{n-2}+...+1\\ &\geq n^n+\binom{n}{n-1}(n-1)^{n-1}+\binom{n}{n-2}(n-2)^{n-2}+...+1 \\ &\geq n^n+(n-1)^{n-1}+ (n-2)^{n-2}+...+1.\end{align}

Answer 3

If $$1+2+・・・+(n-1)^n<n^n$$ when x=n+1 $$1+2+･･･+(n-1)^n+n^n<n^n+n^n<(n+1)^n$$ that inequality works at x=n+1, too.

Answer 4

This looks like the same proof as GAVD, but without sigma notation. I didn't use your lemma explicitly either.

---

Let $P(n)$ be the statement that $1^n + 2^n + 3^n + \dots + n^n < (n+1)^n$. Then $P(1)$ is $1 < 2$, which is definitely true.

Suppose $P(k)$ is true for some $k$. That is, suppose $$ 1^k + 2^k + \dots + k^k < (k+1)^k $$ We want to show $P(k+1)$ is true. Now \begin{align*} 1^{k+1} + 2^{k+1} + 3^{k+1} + \dots + k^{k+1} + (k+1)^{k+1} &\leq(k+1)1^k + (k+1)2^k + \dots + (k+1)k^k \\&\quad\quad+ (k+1)(k+1)^k \\ &= (k+1)\left(1^k + 2^k + \dots + k^k + (k+1)^k\right) \\ &\stackrel{(*)}{\leq} (k+1)\left((k+1)^k + (k+1)^k\right) = 2(k+1)^{k+1} \end{align*} The point marked $(*)$ is where we used the inductive hypothesis. Since $2 < k+1$, we have $$ 1^{k+1} + 2^{k+1} + 3^{k+1} + \dots + k^{k+1} + (k+1)^{k+1} \leq (k+1)^{k+2} $$ which establishes that $P(k+1)$ is true.

Therefore, by induction, $P(n)$ is true for all $n$.

Answer 5

This inequality is obvious if you observe that $$\frac1{(n+1)^{n+1}}\sum_{k=1}^n k^n=\frac1{n+1}\sum_{k=1}^n \Bigl(\frac k{n+1}\Bigr)^{\!n}$$ is the lower Riemann sum for the function $x^n$ on the interval $[0,1]$, with $n+2$ subdivision points. Thus $$\frac1{n+1}\sum_{k=1}^n \Bigl(\frac k{n+1}\Bigr)^{\!n}<\int_0^n x^n\,\mathrm d\mkern1mu x=\frac1{n+1}\iff\sum_{k=1}^n \Bigl(\frac k{n+1}\Bigr)^{\!n}<1.$$