I am looking to prove that for every fixed value of $k$, $ n^{k+1}= O(1^k + 2^k + \cdots + n^k) $
I have already proved that $1^k + 2^k +\cdots + n^k =O(n^{k+1})$ but I don't know how to make the jump to proving the opposite is true. I was thinking that induction might be the way to go (i.e. adding $(n+1)^k$ to each side and simplifying, but the way I did it didn't make anything obvious).
Any help will be very much appreciated.
Thanks, Nolan