CIS 2910 Lecture Notes - Lecture 2: Arithmetic Progression, Summation, Mathematical Induction

• School: University of Guelph
• Department: Computing and Information Science
• Course: CIS 2910
• Professor: Jamileh Yousefi

Document Summary

4i 3: arithmetic, 1+5+9+ +(4n 3) = n(2n 1, base case: (4 3) = (2 1) = 1 n = 1. 1 + 5 + 9 + + (4k 3) = k(2k 1) 1 + 5 + 9 + + (4k 3) + (4(k + 1) 3) = k(2k 1) + (4(k + 1) 3) = 2k2 k + 4k + 1. = [k + 1](2[k + 1] 1) 1: prove the following theorems using mathematical induction: (d) n. 2i = 2n 1, n 1 n = 1. 21 0 = 20 = 21 1 = 1. + 2k 1 + 2k+1 1 = 2k 1 + 2k. 2 2k 1 = 2k+1 1. Qed (f) 4n < (n2 7) for n 6. Ih: n = k k2 7 > 4k. Is: n = k + 1 (k + 1)2 7 = (k2 + 2k + 1) 7 = (k2 7) + 2k + 1.