CPSC 233 Study Guide - Quiz Guide: Mathematical Induction, Irrational Number, Euclidean Algorithm

• School: University of Calgary
• Department: Computer Science
• Course: CPSC 233
• Professor: Tony Tang

Document Summary

[5: use the euclidean algorithm to nd gcd(685, 211) and nd integers x and y so that gcd(685, 211) = 685x + 211y. To nd x and y satisfying gcd(685, 211) = 685x + 211y, gcd(685, 211) = 1. We again see that gcd(685, 211) = 1 = 685(69) + 211( 224). [6: use mathematical induction to prove that. First name (2i 1) = n2 for all integers n 1. n(cid:88) i=1. 2 i=1(2i 1) = 2(1) 1 = 1 and 12 = 1, the base case holds. i=1(2i 1) = k2 for some integer k 1, and show that. Inductive step: assume (cid:80)k (cid:80)k+1 i=1 (2i 1) = (k + 1)2. k(cid:88) k(cid:88) (2i 1) = k+1(cid:88) i=1 i=1 (2i 1) + 2(k + 1) 1 (2i 1) + 2k + 1 i=1. = (k + 1)2 by the induction hypothesis n(cid:88) Thus, (2i 1) = n2 for all integers n 1. i=1.