Proving Polynomial Big-Theta through induction?

Question

I understand the concept of big theta, big oh, and big omega.. I'm just having a hard time proving it. It's been a long time since I've done induction, so I'm pretty sure I'm just rusty and missing something simple.

For example.. the problem I need help with is to show that 5n² - 6n = Θ(n²).

I've gotten the Big-Oh portion of the problem (I do big-Oh and Ω seperately correct?) to:

6k² >= 5n² - 6n

and the big omega portion to:

5n² - 6n >= n²

....but where do I go from here ?! I recall from induction something like... I assume these are true, and now plug in (n+1) for each n and... do.. something? I've lost myself at this point.

Answer 1

To show that 5n^2-6n is O(n^2), you have to prove the statement that 5n^2-6n <= cn^2 for all numbers n >= n0, for some number n0 and constant c.

A proof by induction involves proving the claim for the base case and proving the induction step. In our example, we can see that the base case, when n = 1 clearly holds true for some constant c.

For the induction step, we assume that the claim is true for some number k and use it to show that the claim is true for k+1. So we assume 5k^2-6k <= ck^2 and show:

5(k+1)^2 - 6(k+1)  = 5k^2 +10k + 5 -6k - 6
                   = 5k^2-6k + 10k -1        
                  <= ck^2 + 10k - 1
                  <= ck^2 + c*2k + c       (for any constant c  >= 5)
                   = c(k+1)^2

This proves the claim for k+1 and completes the proof.

You can prove the big Omega claim in a similar way.