Math101 - Lecture 3 revision

[fardell24]

MATH101 – Lecture 3 2 March 2000
Theorems
Implications “if A then B”
Equivalence “A if and only if B” 'If A then B' and then if B then A
Proofs
Direct: use truth A to get truth of B
Contraposition (contradiction) Assumes false to get contradiction
Another variation on equivalence
Proove the following are equivalent
(i) A
(ii) B
(iii) C
Here we need only prove A implies B
B implies C
C implies A !!
Proof by induction
eg Claim: 1 + 2 + 3 + … + n = (1/2)n(n + 1) for all counting numbers n
No use simply checking case n = 1, 2, 3, …
Need induction
Prove for n = 1 – verify
Assume n = k
Proove n = k + 1
There are three steps
Suppose we wish to prove Statement P(n) true for all counting numbers n
1) verify P(1) is true
P (1): 1 = ½ * 1 * (1 + 1) = 1
2) Assume P(n) is true for some n = k. ie we assume p(k) is true
Assume P(k): - 1 + 2 + 3 + … + k = ½ k(k + 1)
3) Use (1) and (2) to prove p(k +1) is true

Theorem:
1 + 2 + 3 + … + n = ½ n(n +1) for counting numbers n
Proof: Let P(n) be the statement
1 + 2 + 3 + … + n= ½ n(n +1)
Use a proof by induction
1) Verify P(1) is true

LHS of P(1) = 1 + 2 + 3 + … + n with n = 1
= 1
RHS of P(1) = ½ n(n +1), with n = 1
= ½ * 1 * (1 +1)
= 1
Therefore LHS P(1) = RHS P(1)

2) Assume P(k) is true

ie assume that 1 + 2 + 3 + … + k = ½ k(k+1) (Inductive hypothesis)

3) Prove P(k + 1) is true given (1) and (2)



LHS P(k + 1) = 1 + 2 + 3 + … + k + (k + 1)
RHS P(k + 1) = ½ (k+1) ((k + 1) + 1_
= ½ (k+1) (k + 2)

LHS = 1 + 2 + 3 + … + k + (k + 1)
= ½ k (k + 1) + (k + 1), using the inductive hypothesis
ie use Step 2
= (k + 1) (½ k + 1)
= (k +1) ½ (k +1)
= ½ (k+1)(k+2)
= RHS p(k +1)
We have a proof by induction

Theorem: Proove for any counting number n greater than 9 that 2^n > n^3
Use induction
1) verify P(1Φ)

LHS P(10) = 2^10
= 1024
RHS P(10) = 10 ^ 3
= 1000

Therefore LHS P(10) > RHS P(10)
Therefore P(10) is true

2) Assume P(k) ((k > 9) is true
ie assume 2^k > k ^ 3, k ^ 9

3 Prove P(k + 1) is true
LHS P(k + 1) = 2^(k + 1)
RHS P(k +1) = (k + 1) ^ 3
Now LHS P(k + 1) = 2 ^ (k + 1)
= 2 ^ k * 2
= 2 * 2 ^ k
2 * 2 ^ k > 2 * k ^ 3, using step 2
ie LHS P(k + 1) > 2 * k ^ 3
Now RHS (k + 1) = (k + 1) ^ 3
= k ^ 3 + 3 * k ^ 3 + 3k + 1
But, 3 k + 3*k^3 + 1 < k^2 + 3*k^2 + k ^ 2 (no 1 < k ^ 2 for k > 1)
3k < k ^ 2 for k ^ 3
3 < k ie 3k + 3*k^2 + 1 < 5*k^2 < k*k^2, for k > 5
3k < k ^ 2

Therefore RHS (k +1) = k^3 + 3*k^2 + 1 + 3k < k^3 + k^3 < 2*k^3
Therefore RHS(k + 1) < LHS (k +1)
Therefore RHS(k + 1) is true