Prove by induction that for every integer n 2 1: 1(1!) + 2(2!) + 3(3!) + ... + n(n!) = (n+ 1)! -1 (here n! = nx (n- 1) x .. x2x1for any integer n21) Consider the following recursive program that follows (roughly) Euler's Method for computing the GCD of two numbers: Int GCD(Int n, int k) |/ Function to compute GCD(n,K) ; We want n> =k Initially { f (k -= 0) return n: // Base Case F (nzk) { If (k z n-k) return GCD( k , n-k) ; I/ Before we subtract k from n we want the larger of this result and k to go f else return GCD(n -k, k ) II ff n-k is larger we put it first else return GCD(n , k-n ) : I/ the good case a) Write down the sequence of function calls produced by this algorithm when n: -90 and k = 48. b) Give a big O approximation in terms of n (assume that n> k initially) for the number of functions calls that will result from Initially calling GOD(n,k) . Hint: Look backwards at the sequence of numbers produced by this algorithm; In reverse we see a familar pattern