10 points A recursive algorithm generally solves a class of problems of varying sizes. (Defining "size" can be part of the challenge of designing the algorithm.) The algorithm explicitly specifies the solution for the smallest problems. For larger problems, it gives instructions for generating a smaller problem or some smaller problems, says to solve the smaller problems by using the algorithm itself, and gives instructions on how to combine the solutions of the smaller problems to solve the larger problem. For example, the Euclidean algorithm for finding the greatest common divisor of two non-negative integers a and b can be specified as a recursive algorithm as follows. recursive gcd(b,a) algorithm: if a=0 then the answer is b. otherwise the answer is gcd(a,bmoda) Strong induction can be often used to prove the correctness of a recursive algorithm. For example, if the sizes are positive integers, the proposition P(n) to be proved is that the algorithm performs correctly on problems of size n. The base cases are the the solutions for problems of the smallest sizes. The inductive step P(1)P(2)P(k)P(k+1) says that if the the algorithm performs correctly for all smaller problems than problems of size k+1, then it performs correctly on problems of size k+1. Please give a proof by strong induction of the correctness of the Euclidean algorithm above. Please include your definition of the size of the problem in terms of a and b. 10 points A recursive algorithm generally solves a class of problems of varying sizes. (Defining "size" can be part of the challenge of designing the algorithm.) The algorithm explicitly specifies the solution for the smallest problems. For larger problems, it gives instructions for generating a smaller problem or some smaller problems, says to solve the smaller problems by using the algorithm itself, and gives instructions on how to combine the solutions of the smaller problems to solve the larger problem. For example, the Euclidean algorithm for finding the greatest common divisor of two non-negative integers a and b can be specified as a recursive algorithm as follows. recursive gcd(b,a) algorithm: if a=0 then the answer is b. otherwise the answer is gcd(a,bmoda) Strong induction can be often used to prove the correctness of a recursive algorithm. For example, if the sizes are positive integers, the proposition P(n) to be proved is that the algorithm performs correctly on problems of size n. The base cases are the the solutions for problems of the smallest sizes. The inductive step P(1)P(2)P(k)P(k+1) says that if the the algorithm performs correctly for all smaller problems than problems of size k+1, then it performs correctly on problems of size k+1. Please give a proof by strong induction of the correctness of the Euclidean algorithm above. Please include your definition of the size of the problem in terms of a and b