## Question

###### Problem 2. (24 points) Use induction to prove that for any n 2 1, if a > b 2 1 and Euclid(a,b) takes n iterations then a > fn+2 and b > fn+l where fn is the nth term of Fibonacci sequence:hint: Consult with the slides and posted video for the lecture 20.Problem (15 points) Prove the following corollaries where fn is the nth term of Fibonacci sequence. (A Corollary is proposition that follows from proved theorem:) a) Corollary 1: For all n > 1 if a > b 2 1 and b < fn+l then Eucl

Problem 2. (24 points) Use induction to prove that for any n 2 1, if a > b 2 1 and Euclid(a,b) takes n iterations then a > fn+2 and b > fn+l where fn is the nth term of Fibonacci sequence: hint: Consult with the slides and posted video for the lecture 20. Problem (15 points) Prove the following corollaries where fn is the nth term of Fibonacci sequence. (A Corollary is proposition that follows from proved theorem:) a) Corollary 1: For all n > 1 if a > b 2 1 and b < fn+l then Euclid(a,6) takes fewer than iterations_ hint: Consult with the slides and posted video for the lecture 20. Use the theorem in problem to prove Corollary To prove Corollary 1, do not use induction. b) Corollary 2: For all n > 2 if a < fn or b < fn then Euclid(a,b) takes strictly fewer than n iterations hint: Consult with the slides and posted video for the lecture 20. Use the theorem in problem 2 and Corollary 1to prove Corollary 2. To prove Corollary 2, do not use induction.