Hello! Please provide the answers for each problem please.

Math 197/208 Homework 1 8/27/2021 - Due 9/3/2021 Define the sequence { Fn. | n 2 0} of Fibonacci numbers as follows: Fo = 0, F1 = 1, Fn = Fn-1+Fn-2 for n > 2. Use induction to prove the following. 1. For every n 2 1, god(Fn+1, Fn) = 1. Hint: Use the Euclidean algorithm. 2. From the previous problem, we can deduce that sFn+1 + tFn = 1 for some s, te Z. Prove that (s, t) = ((-1)"-1En-2, (-1)" Fn-1) satisfy this equation. 3. For all m > 0, n 2 1, Fmen = Fm+iFn+FmFn-1. Hint: Fix any m 2 0 and do the induction on n only. 4. Prove that if n | m then Fn | Fm. Hint: Use the result of the previous problem with m = kn, and do the induction on k. 5. Prove that if d = gcd(a, b), then Fa = gcd(Fa, Fb). Hint: Use the previous problems and the Euclidean algorithm. Show that if a = bq +r, where q, r E Z, q 2 0, 0