Fibonacci numbers were defined as follows: f0 = 0, f1 = 1 and for all n 1, fn+1 = fn + fn1. i. For any natural number n 3, show that the quotient of fn+1 fn is 1 and the remainder of fn+1 fn is fn1. ii. Prove (by induction/recursion, if you like) that the Euclidean Algorithm takes n 2 loops to calculate gcd(fn, fn1), for any integer n 3.