Topic 3: Proof

Question 1

What is a definition, theorem, lemma and corollary (4)

Answer 1

-A definition introduces/explains content
-A theorem is a key mathematical result
-A lemma is a minor mathematical result, usually preparing for a theorem
-A corollary is a consequence of a theorem

Question 2

What is a proposition, hypothesis and proof (3)

Answer 2

-A proposition is a statement
-A hypothesis is an unproven result
-A proof is an argument used

Question 3

What are different methods of proof (6)

Answer 3

-Direct proof (start with hypothesis, form an unbroken chain of logic, lead to a desired fact)
-Proof by contradiction (assume desired result is false, then show this leads to contradiction)
-Proof by exhaustion (check all possible causes)
-Proof by demonstration (provide a concrete example for an existence theorem)
-Disproof by counter example (find one concrete example that doesn’t satisfy the statement)
-Proof by induction (useful for providing general statements about natural numbers)

Question 4

What is the principle of mathematical induction (2,2)

Answer 4

-Suppose we have a mathematical statement p(n) which depends on some n ∈ ℕ
-If p(1) is true, and p(k) ⇒ p(k+1), it follows p(n) is true for all n ∈ ℕ
-Verification of p(1) is the induction base
-Proving p(k) ⇒ p(k+1) is the induction step

Question 5

How can we prove Σk = 0.5(n)(n+1) with proof by induction (3,5,1)

Answer 5

-First check the induction base
-Let n = 1, Σk = 1 and 0.5(1)(1+1) = 1
-Statement is true for n =1

-Now suppose p(k) is true for some k ∈ ℕ (induction step)
-Sk = Σi = 0.5k(k+1)
-S(k+1) = Σi + (k+1)
-S(k+1) = 0.5k(k+1) + (k+1)
-S(k+1) = (k+1)(0.5k+1) = 0.5(k+1)(k+2) which is the required expression on the RHS

-Therefore, p(1) is true and p(k) implies p(k+1) for all k ∈ ℕ

Question 6

How can we show 5ⁿ - 1 is divisible by n using proof by induction (1,1,6)

Answer 6

-Let p(n): 5ⁿ - 1 is divisible by 4

-Induction base: 5⁽¹⁾ - 1 = 4 -> divisible by 4

-Induction step: Assume p(k) is true for some k ∈ ℕ
-5^k - 1 = 4m for some m ∈ ℤ, so that 5^k = 4m + 1
-Then 5^(k+1) - 1 = 5(5^k) -1
-5(5^k)-1 = 5(4m+1) -1
-5(4m+1) - 1 = 20m + 4 = 4(5m+1)
-This is divisible by 4, and hence p(k) => p(k+1), and the result is therefore true by proof of induction