Big O Proof

[RK4]

Hi all! I'm supposed to prove the following:

 

Suppose that m is a positive real number. Show that Sigma(j^m), j runs from 1 to n is O(n^(m+1)).

 

So we have:

 

Sigma(j^m), j runs from 1 to n = 1^m + 2^m + 3^m + . . . + n^m

 

I think we should use induction on m here to prove this.

 

Basis Step:

 

m = 1

 

This is definitely true for m = 1 because we have

 

Sigma(j^1), j runs from 1 to n = n(n+1)/2 which is O(n^2)

 

Now, O(n^2) = O(n^(1+1) = O(n^(m+1)

 

Inductive Step:

 

Assume Sigma(j^m), j runs from 1 to n is O(n^(m+1)) to be true. That is, it is true for m = n. (Inductive Hypothesis)

 

Then must show it is also true for m = n + 1:

 

Sigma(j^m), j runs from 1 to n + 1

 

= Sigma(j^m), j runs from 1 to n + j^(n+1)

 

= O(n^(m+1)) + j^(n+1) (By Inductive Hypothesis)

 

= . . .

 

At this point how do I conclude that the whole thing is O(n^(m+1))?

 

Any help will be appreciated. I'm trying to get a hold of these big O proofs.