Mathematical Logic and Proving Techniques Lecture Notes

Exercise 3.53 March 2012 Q6 Use mathematical induction to prove that for every positive integer ������ ≥ 2. 2(2!) + ⋯ + ������(������!) = (������ + 1)! − 2 195

Exercise 3.54 March 2013 Q10 Use mathematical induction to prove that for every integer ������ ≥ 0 0y + 1y + 2y + 3y + ⋯ + ������y = ������(������ + 1)(2������ + 1) 6 196

Exercise 3.55 September 2013 Q9 Prove by mathematical induction that for all ������ ≥ 1 and ������ ∈ ������G, j − 1) = ������(3������ + 1) 2 ú(3������ ûü¬ 197

Exercise 3.56 March 2014 Q10 Use mathematical induction to prove that 1k + 2k + ⋯ + ������k = \"������(������2+ 1)#y whenever ������ is a positive integer. 198

Exercise 3.57 September 2014 Q9 a) Use mathematical induction to prove that 2y + 5y + 8y + ⋯ + (3������ − 1)y = 1 ������(6������y + 3������ − 1) for all natural number ������ 2 b) Hence, use the result found in (a) to evaluate 4 + 25 + 64 + ⋯ + 37636. 199

Exercise 3.58 March 2015 Q9(b) Use Mathematical Induction to prove that for each natural number, ������, 1 + 2 ∙ 2 + 3 ∙ 2y + ⋯ + ������2jI¬ = (������ − 1)2j + 1 200

Exercise 3.59 September 2015 Q10 Use Mathematical Induction to prove that for each natural number ������, 4 + 2 ∙ 7 + 3 ∙ 10 + ⋯ + ������(3������ + 1) = ������(������ + 1)y 201

Exercise 3.60 March 2016 Q10 Use Mathematical Induction to prove that for each natural number n, j (4������ − 1 + 3) = ������ 1 3)(4������ 4������ + ú ûü¬ 202

Exercise 3.61 October 2016 Q10 Use mathematical induction to prove that for every integer ������ ≥ 1, j = 5j − 1 4 ú 5ûI¬ ûü¬ 203

Exercise 3.62 March 2017 Q10 Prove by using the Mathematical Induction Method: If ������ ∈ ������ and ������ ≠ 1, then for every ������ ≥ 0, ������¼ + ������¬ + ������y+. . . +������j = ¬Iÿ$%& ¬Iÿ 204

Exercise 3.63 January 2018 Q10 Prove the following statement is true for all positive integers n using Mathematical Induction. j ú ������œ2û• = 2 + (������ − 1)2jG¬ ûü¬ 205

Exercise 3.64 December 2018 Q10 Use mathematical induction to prove that for each natural number ������, 1 ∙ 1! + 2 ∙ 2! + 3 ∙ 3! + ⋯ + ������ ∙ ������! = (������ + 1)! − 1 206

Exercise 3.65 June 2019 Q10 Use mathematical induction to prove: (11)j − 6 is divisible by 5 for every positive integer ������. 207

3.10 Summary The following figure summarizes the proving method that is used when dealing with statements containing quantifiers and negation. Types of Statement Quantifier Negation Existential Universal Contradiction 'there is' 'for all' Construction Choose Contrapositive (backward) method (backward) Forward- Specialization backward method (forward) (forward) Induction (for all ������ > 0) 208

Exercise 3.66 September 2014 Q8(a) State the method of proof used in proving the conditional statement ������ → ������ if the following statements are encountered. i) B: For every \"object\" with a \"certain property,\" \"something happens.\". ii) A: For all \"objects\" with a \"certain property,\" \"something happens,\". iii) B: There is an \"object\" with a \"certain property\" such that \"something happens.\". iv) B: For every integer ������ ≥ 1, \"something happens,\" where statement ������(������) is true. v) Work forward from NOT B and backward from NOT A. 209

Exercise 3.67 March 2015 Q7 Determine whether the suggested method is ‘true’ or ‘false’ with the respective proposition. If it is ‘true’ briefly explain why and state the appropriate method to be used if it is ‘false’. a) Method: Forward-backward Proposition: If ������ and ������ are odd integers, then the equation ������y + 2������������ + 2������ = 0 has no rational solution for ������. b) Method: Contrapositive Proposition: If ������ is a function defined by ������(������) = 2Ø + 3������, then there is a real number ������∗ between 0 and 1 such that for all ������, ������(������∗) ≤ ������(������). c) Method: Mathematical Induction Proposition: For every integer ������ ≥ 4, ������! > ������y. d) Method: Specialization Proposition: If ������ and ������ are convex sets, then ������ ∩ ������ is a convex set. 210

211

212



references Ralph P. Grimaldi (2004). Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition. Addison Wesley Daniel Solow (2010). How to Read and Do Proofs: An Introduction to Mathematical Thought Processes, 5th edition. John Wiley & Sons. Charles E. Roberts, Jr. (2010). Introduction to Mathematical Proofs: A Transition. CRC Press. Image credit: Low Angle of Colorful Glass Panels Under Blue Sky by Scott Webb, Pexels