(b) Write a recurrence for this algorithm and solve it to obtain a tight upper bound on the worst case runtime of this algorithm. You can use any method you like for solving this recurrence.

Problem 2. Consider the algorithm below for finding the total sum of the numbers in any array A[1:n). TOTAL-SUM(A[1 : n]): 1. If n = 0: return 0. 2. If n = 1: return A[1]. 3. Otherwise, let mi + TOTAL-SUM(A[1 : 2]) and m2 + TOTAL-SUM(A[2 +1:n]). 4. Return mi + m2. We analyze TOTAL-SUM in this question. (a) Use induction to prove the correctness of this algorithm. (10 points)