Prove by induction that $\sum_{k=1}^nk^p < (n+1)^{p+1}/(p+1), \quad n,p \in \mathbb{N}$ 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.
 A: 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$$
A: 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}
