Solving a problem on assignment 3

I will now attempt to write out my thought process in solving problem 3 of assignment 3.

1. UNDERSTANDING THE PROBLEM 
Prove or disprove: 15n2 is in Ω (3x 2ⁿ).
I know that f(n) in Ω(g(n)) means that after a certain n, f(n) is always larger than g(n).
First I need to figure out if this statement is true or not, so for help, I decided to graph the two lines.

It was obvious that while 15x² started off outputting bigger, 3* 2^x eclipsed it later on. Which means that that the statement is wrong.
2. DEVISING A PLAN
I knew that in order to prove that the statement was wrong, I needed to prove the contrapositive of the statement, which is: ∀c ∊ ℝ, ∀B∊ ℕ, ∃n∊ ℕ, n  ≥ B ⋀ g(n)  < c f(n).
With a little help from the hint from the question, I figured out that I need to use limits and l’Hopital’s rule to prove using the definition of a limit that g(n) < c f(n).

3. CARRYING OUT THE PLAN
I start out my proof as usual, assuming the ∀s.

Assume c ∊ ℝ⁺ and B ∊ ℕ.   

I want to show that the limit as n → ∞ (15n²/3 x 2ⁿ) is zero which would prove that the denominator, 3 x 2ⁿ is exponentially larger than the numerator (15n²), thus making the claim that 15n² is bigger than 3 x 2ⁿ false after a certain n.

Let L = lim_{n →∞} 15n² / 3 x 2ⁿ

Then L = lim_{n →∞} 30n / 3ⁿ x 2^n-1         # L’Hopital’s Rule

Then L = lim_{n →∞} 30 / 3n² - 3ⁿ x 2^n-2     # L’Hopital’s Rule Again

Then L = 0     # 1/∞ = 0

Now I will write out the definition of a limit, and note that because c and ε are both ∊ ℝ⁺_, we can make c = ε.

Then ∃n0 ∊ ℕ, ∀n ∊ ℕ, n ≥ n0 ⇒ L - c < 15n2 / 3 x 2n < L + c    

Since L = 0,

Then ∃n₀ ∊ ℕ, ∀n ∊ ℕ, n ≥ n₀ ⇒ 15n2 < c (3 x 2n)

Let n₀ be such that ∀n ∊ ℕ, n ≥ n₀ ⇒ 15n2 < c (3 x 2n), and n’ = max (B, n₀)

Since B and n₀ are both ∊ ℕ:

Then n’ ∊ ℕ

Then n’ ≥ B        #By Definition of max

Then 15n’2 < c3 x 2n’     #By the lines above, since n’ ≥ n₀

Now let 2 functions g(n’) = 15n’², and f(n’) = 3 x 2^n’

Then n’ ≥ B ⋀ g(n’)  < c f(n’)    # ⋀ intro, g(n’) = 15n’², and f(n’) = 3 x 2^n’

Then ∃n∊ ℕ, n ≥ B ⋀ g(n)  < c f(n)    # ∃ intro

Conclude ∀c ∊ ℝ, ∀B∊ ℕ, ∃n∊ ℕ, n ≥ B ⋀ g(n)  < c f(n)     # ∀ intro

I have now proved the contrapositive, thus disproving the original statement.

4. LOOKING BACK

Let’s check the answer by observing the 2 functions at xs with high expected y, say x = 10:

15(10) ² = 1500.

3(2)¹⁰ = 3072.

And x = 11:

15(11) ² = 1815.

3(2)¹⁰ = 6144.

So it is obvious that 3(2)¹⁰ is NOT the lower bound for 15(10) ² because 3(2)¹⁰ is obviously growing at a much faster rate than 15(10) ².

Although there may be other solutions to solve this problem, I think this method, using limits is the easiest and cleanest method.