2. [12 marks] The binary method of exponentiation computes an for any positive integer n using the fact that a"- (a/2)2 if n is even, and a"-a a-1 if n is odd (a) [6 marks] Give the pseudocode for a recursive algorithm computing a" where n is a positive integer, using the above idea. Do NOT use memoization. In your solution, when n is even, there should be only one (explicit) recursive call among your pseudocode for this case. For this sub-question, no explanation, justification, or analysis is required; simply give your pseudoc ode. (b) [6 marks] Find out the exact total number of multiplications performed when using your algorithm to compute an for any positive integer n. Use the substitution method, i.e., make a guess and then prove its correctness by induction. Hint: It may be helpful to consider the number of 1-digits in the base-2 expression of n. Let s2(n) be this value. You can use s2(n) as one of the additive terms in your solution