Big O Proof Check

Forums: Science And Math
Email this Topic • Print this Page

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.

Topic Stats
Top Replies
Link to this Topic

Type: Discussion • Score: 1 • Views: 576 • Replies: 4

No top replies

Looks like either no one knows or no one cares...

0 Replies

Shoulda asked me 25 years ago.

0 Replies

I think the proof is trivial.
Let j, m, n be positive integers. then:

we know that if j < n then j^m < n ^ m
therefore Sigma(j^m) (j runs from 1 to n) < n.n^m
therefore Sigma(j^m) (j runs from 1 to n) < n^(m+1)

0 Replies

coolamit wrote:

I think the proof is trivial.
Let j, m, n be positive integers. then:

we know that if j < n then j^m < n ^ m
therefore Sigma(j^m) (j runs from 1 to n) < n.n^m
therefore Sigma(j^m) (j runs from 1 to n) < n^(m+1)

This isn't some Kindergarten proof. Here's a more apt proof:

Claim:

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

Proof:

So we have:

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

If Sigma(j^m), where j runs from 1 to n is O(n^(m+1)),

then

Sigma(j^m), where j runs from 1 to n < = K * n^(m+1), for K being a positive constant

Therefore,

1^m + 2^m + 3^m + . . . + n^m < = K * n^(m+1)

Now, since an exact sum of the series on the left hand side isn't possible we will approximate its sum by:

/
| u^m du, from 0 to n
/

So, we have:

/
| u^m du, from 0 to n < = K * n^(m+1)
/

n^(m+1) / (m+1) <= K * n^(m+1)

1/(m+1) * n^(m+1) <= K * n^(m+1)

And so it is clear that for this inequality to hold K must be greater than or equal to

1/(m+1).

So, K > = 1/(m+1).

Done!

0 Replies

Big O Proof Check

Related Topics

Quick Links

My Account

able2know