Proof of asymptotic relation $\sum_{i=1}^n i^k = \Theta(n^{ k+1} )$

191 Views Asked by At

I'm doing an exercise to proof that $\sum_{i=1}^n i^k = \Theta(n^{ k+1} )$

I proved that $\sum_{i=1}^n i^k = O(n^{k+1})$, but I can't prove that is $\Omega(n^{k+1})$

I'm trying to do it by induction but still stuck to show that $cn^{k+1} + (n+1)^k \le c(n+1)^{k+1}$.