Week #10
Topic: big-Omega, big-Theta,
general properties
I had mentioned before that this course has some
similarities with MAT137. When analyzing this week’s material I realized that
the connection between these two courses is really strong. For instance, the new
bound that combines both big-Omega and big-Theta looks very similar to the
mathematical concept of Pinching theorem. Also, the way in which we proved the
general statements about two functions is quite similar to proving limit laws. In
the following part I will try to show how related CSC165 AND MAT137 are.
CSC 165
·
f ∈ O1 (g)
{f: ℕ ↦ ℝ≥0 | ∃ c1 ∈ ℝ+, ∃ c2 ∈ ℝ+, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ c1 g(n) ≤ f (n) ≤ c2
g(n)}
Application
Let’s apply this concept to – (n2) < 0
< n2 in which case n is any typical natural number, c1 = 1, c2 = -1, and
B ≥ 0
MAT 137
·
Pinching Theorem
Let f, g, h be functions
If ∃ p > 0 such that 0 < |n –a | <
p and
g(n) ≤ f (n) ≤ h(n) and the limit of
both g(n) and h(n) are the same as n approaches a.
Then, the
limit of f(n) as n approaches a is the same as the ones above
Application
x < x sin(1/x)
< -x
Connection: If we look at the graph that deals
with the pinching theorem we notice that ∀ x ∈ ℕ when B ≥ 0, x
sin(1/x) is between x and –x or what is the same, between c1x and
c2x, in which case c1 is 1 and c2 is -1.
Exactly as happens with the new bound learned this week.
PROOFS
CSC165
Prove F = {f: ℕ ↦ ℝ≥0} ∀ f, g, h ∈ F,
(f ∈ O(h) ∧ g ∈ O(h)) ⇒ f + g ∈ O(h)
Assume f, g, h ∈ F # Introduce ∀
Assume (f ∈ O(h) ∧ g ∈ O(h)) #Antecedent
Then ∃ cf ∈ ℝ+, ∃ Bf ∈ ℕ, ∀ n ∈ ℕ, n ≥ Bf ⇒ f(n) ≤ cf * (h(n))
Then ∃ cg ∈ ℝ+, ∃ Bg ∈ ℕ, ∀ n ∈ ℕ, n ≥ Bg ⇒ g(n) ≤ cg * (h(n))
Prove ∃ c ∈ ℝ+, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ f(n) + g(n) ≤ c * (h(n))
Pick c = cf + cg. Then c ∈ ℝ+
Pick B = max (Bf, Bg). Then B ∈ ℕ
Assume n ∈ ℕ, n ≥ B
Then (f + g) (n) = f(n) + g(n) ≤ cf * (h(n)) + cg *
(h(n))
#By assumption n≥ B, n ≥ Bf and n ≥ Bg
≤
(cf + cg) * (h(n))
=
c * (h(n)) # c = cf + cg
Conclude ∀ f, g, h ∈ F, (f ∈ O(h) ∧ g ∈ O(h)) ⇒ f + g ∈ O(h)
MAT 137
Prove If the limit of f(x) as x approaches a is equals L and the limit of g(x) as x approaches a is equals M. Then the limit of f(x) + g(x) as x approaches a is equal to L + M
Asume = L and the limit of f(x) as x approaches a is equals L and the limit of g(x) as x approaches a is equals M.
Then ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x – a | < d ⇒ |(f(x)) - L| <
e1 = e/2
Then ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x – a | < d ⇒ |(g (x)) - M| <
e2 = e/2
Prove ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x – a | < d ⇒ |(f(x) + g(x)) – (L
+ M)| < e
Assume e ∈ ℝ
Take d= min(d1, d2)
Assume x ∈ ℝ ∧ |x – a | < d
Then |(f(x) + g(x)) – (L + M)| = |(f(x) - L) + (g(x) - M)| ≤ |(f(x) - L)| + |(g(x)
- M)|
= e/2 + e/2 = e
Conclude ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x – a | < d ⇒ |(f(x) + g(x)) – (L + M)| < e
Connection
In both cases,
we assumed two things and used our assumptions to prove the final result. Even
though these two proofs prove something completely different, they follow the
same principle and use the same tools
