proving big o for a given equation
I would just like to prove the following: Show that 1^k + 2^k+...+n^k is O(n开发者_JS百科^(k+1)) for every positive integer k
I am not sure how to go about it. Normally when I am proving a function is big O of another function I find constants c,k such that f(x)<=cg(x) for all x>k. I don't think that this approach would work in the above example.
1^k + 2^k+...+n^k <= n^k + n^k + .... + n^k = n * n^k = n^(k+1)
精彩评论