# Proof by induction: $\sum_{j=1}^{n-1}{j^k}<\frac{n^{k+1}}{k+1}$ with $n,k \in \mathbb{N}$ and $n\geq 2$

Proof by induction: $$\sum_{j=1}^{n-1}{j^k}<\frac{n^{k+1}}{k+1}$$ with $$n,k \in \mathbb{N}$$ and $$n\geq 2$$

Inductive step: $$\sum_{j=1}^{n}{j^k}<\frac{(n+1)^{k+1}}{k+1}$$$$\Bigg(\sum_{j=1}^{n-1} j^k \Bigg)+n^k<\frac{(n+1)^{k+1}}{k+1}$$$$\frac{(n+1)^{k+1}}{k+1}+n^k<\frac{(n+1)^{k+1}}{k+1}$$ How can I continue???

• I think there's one too many $+1$. But the simplest way I see how to continue this is Bernoulli's Inequality. Do you have that to use? – Robert Wolfe May 9 at 12:35
• Are you sure you're matching the inductive hypothesis? And as for the next step, after you've fixed your previous steps, you can simply expand the right side using the binomial expansion theorem. – Simply Beautiful Art May 9 at 12:43
• Is induction required or is another way also accepted? – trancelocation May 9 at 12:54

Actually, you made a small error, when you replaced the sum from the second line to the third. The reasoning should be the following, I'll let you find your error:

We have: $$\sum_{j=1}^{n} j^k = \sum_{j=1}^{n-1} j^k + n_k <\frac{n^{k+1}}{k+1} + n^k$$

We want: $$\frac{n^{k+1}}{k+1} + n^k < \frac{(n+1)^{k+1}}{k+1} \\ \leftrightarrow n^k < \frac{(n+1)^{k+1} - n^{k+1}}{k+1}$$

and by expanding the exponent, we get:

$$(n+1)^{k+1} = \sum_{i=0}^{k+1} \pmatrix{k+1\\i}n^i = n^{k+1} + (k+1) n^k + \sum_{i=0}^{k-1} \pmatrix{k+1\\i}n^i$$

Therefore:

$$\frac{(n+1)^{k+1} - n^{k+1}}{k+1} = n^k + \frac{1}{k+1} \sum_{i=0}^{k-1} \pmatrix{k+1\\i}n^i > n^k$$

And it's done!

Final line should have $$n^{k+1}$$ as numerator not $$n+1$$. After that you should check $$n^{k+1}+n^k(k+1) < (n+1)^{k+1}$$. If you binomially expand the right hand side you can see the left hand side is like the final 2 terms in the series. The inequality follows

• $n^{k+1}+n^k(k+1) < (n+1)^{k+1}=\left(\sum_{j=0}^{k}{\begin{pmatrix} k \\ j \end{pmatrix}}1^{k-j}\cdot n^j\right)\cdot (n+1)$ ???? – Analysis May 9 at 12:49
• Actually do the right hand side as binomial series but with the terms going up to $k+1$, you are on the right lines however. – George Dewhirst May 9 at 12:51