Let k be a positive integer. Show that 1^k+2^k+...+n^k is O(n^(k+1)).

I am stuck on this problem for my discrete math class. Any help would be greatly appreciated.

Note that
1^k + 2^k + ... + n^k
≤ n^k + n^k + ... + n^k
= n * n^k
= n^(k+1) for all n ≥ 1.

Hence 1^k + 2^k + ... + n^k is O(n^(k+1)).

I hope this helps!