Please provide proof in paragraph form

Problem 3. (25 points) Define Euclid's GCD algorithm as follows: def Euclid (a, b) : while b > 0: , b = b, axb return a (If you are unfamiliar with Python, this means that we will start with some inputs (a, b) and will replace (a, b) with (b, r), where r is the remainder of a when divided by b. We will do so repeatedly, as long as b > 0. If we start with b = 0, we will do nothing. Once b = 0, we will output a.) We already proved that this algorithm computes god(a, b) because god(a, b) = god(b, a mod b) and because god(a, 0) = a. We will now analyze how long it takes, in a few steps. Here's the first step. a) (20 points) Let fo = 0, f1 = 1, In+2 = fat1 + In for n 2 0 be the Fibonacci sequence. Use induction to prove the following. For any n 2 1, if . a and b are integers; Da>b . b>1; . Euclid(a, b) takes n iterations then a 2 fn+2 and b 2 fn+1. Hint: Be careful with the inductive case: you need to prove that all four conditions above are satisfied before you can use the inductive hypothesis. The division theorem is going to help you with that. Note that you have three conditions and two things two prove. b) (5 points) Prove that for any integer n 2 1, if a > b 2 1 and b