Prove by induction that $\sum_{k=1}^nk^p < (n+1)^{p+1}/(p+1), \quad n,p \in \mathbb{N}$

Question

For $n=1$, we have at the left side $1^p$, and at the right side: $$ \frac{2^{p+1}}{p+1}\mathrm{~which~is } >1$$ so it holds for $n=1$, but how can we prove that $$ \sum_{k=1}^{n+1}k^p<\frac{(n+1)^{p+1}}{p+1}+(n+1)^p \stackrel{(?)}{<}\frac{(n+2)^{p+1}}{p+1}$$ I don't know how to get to the last part of inequality.

Answer 1

The last inequality should be $$\frac{(n+1)^{p+1}}{p+1} + (n+1)^p \leq \frac{(n+2)^{p+1}}{p+1}$$

and that follows from $$(n+2)^{p+1} = ((n+1)+1)^{p+1} = (n+1)^{p+1} + (p+1)(n+1)^p + \binom{p+1}{2}(n+1)^{p-1} + \dotsb \geq (n+1)^{p+1} + (p+1)(n+1)^p$$

Answer 2

Although I would suggest Ihf's recommended route via calculus, and even though Catalin's answer contains one of the key insights, there still is a way to prove the given inequality using double induction.

---

Claim: For all $n,p\in\mathbb{N}$ $$ \sum_{i=1}^n i^p < \frac{(n+1)^{p+1}}{p+1}. $$

Proof. Let $S(p,n)$ be the inequality in the statement of the claim. First, it is proved for all $p\geq 1$ that $S(p,1)$ is true.

Base step: The statement $S(1,1)$ is true since $1<2$.

Inductive step (inducting on $p$): Fix some $k\geq1$, and assume that $S(k,1)$ is true; that is, $\sum_{i=1}^1 i^k<\frac{2^{k+1}}{k+1}$. Beginning with the left-hand side of $S(k+1,1)$, $$ \sum_{i=1}^1 i^{k+1}=1^{k+1}=1^k<\frac{2^{k+1}}{k+1}<\frac{2^{k+2}}{k+2}, $$ we reach the right-hand side of $S(k+1,1)$. Hence, $S(k,1)\to S(k+1,1)$, and so by mathematical induction, for all $p\geq1$, $S(p,1)$ is true.

Fix an arbitrary $p_0$. Then $S(p_0,1)$ is true and so this is a base step for proving for all $n$ that $S(p_0,n)$ holds.

Inductive step (inducting on $n$): This step is of the form $S(p_0,\ell)\to S(p_0,\ell+1)$. Let $\ell\geq1$ be fixed and assume that $S(p_0,\ell)$ is true; that is, $\sum_{i=1}^\ell i^{p_0}<\frac{(\ell+1)^{p_0+1}}{p_0+1}$. Beginning with the left-hand side of $S(p_0,\ell+1)$, \begin{align} \sum_{i=1}^{\ell+1}i^{p_0}&= \sum_{i=1}^{\ell}i^{p_0}+(\ell+1)^{p_0}\tag{by definition}\\[1em] &< \frac{(\ell+1)^{p_0+1}}{p_0+1}+(\ell+1)^{p_0}\tag{ind. hyp.}\\[1em] &= \frac{(\ell+1)^{p_0+1}+(p_0+1)(\ell+1)^{p_0}}{p_0+1}\tag{simplify}\\[1em] &< \frac{(\ell+2)^{p_0+1}}{p_0+1},\tag{bin. thm. $(\dagger)$} \end{align} we reach the right-hand side of $S(p_0,\ell+1)$. Hence, by induction, for each fixed $p_0$ and all $n\geq1$, we see that $S(p_0,n)$ is true, completing the inductive step.

Since $p_0$ was arbitrary, by induction, for all $n,p\in\mathbb{N}$ the statement $S(p,n)$ is proved. $\blacksquare$

---

$(\dagger)$: The step in the proof that used the binomial theorem (as is explicated in Catalin's answer) may be seen as a reverse engineering of sorts: \begin{align} (\ell+2)^{p_0+1}&=[(\ell+1)+1]^{p_0+1}\\[1em] &=\sum_{i=0}^{p_0+1}\binom{p_0+1}{i}(\ell+1)^{i}1^{p_0+1-i}\\[1em] &= (\ell+1)^{p_0+1}+(p_0+1)(\ell+1)^{p_0}+\sum_{i=0}^{p_0-1}\binom{p_0+1}{i}(\ell+1)^{i}1^{p_0+1-i}\\[1em] &> (\ell+1)^{p_0+1}+(p_0+1)(\ell+1)^{p_0}. \end{align}