Please answer the following questions using the instructions given and provide some justification.

Exercise 3 (25 points) Proof by induction Let us prove this formula: S1- 1-a a) (4 points) Try this expression with a 2 and n 4. Find S using the two expressions (the sum and the fraction). Let us prove this expression using induction a. (5 points) Show the base (basis) case b. Show the induction step by answering these questions: b) i. (4 points) What is your hypothesis to use for the induction step? i. (12 points) Now, complete the induction step Exercise 4 (35 points) Loop Invariant Consider the naive sorting algorithm we presented in Module l: Sort-Array (A) for j = 1 to (A.length- 1) for i (j1) to A.length // swap Ali] and A(5] buffer Aj] A[1] = buffer The objective is to prove that the above sorting algorithm is correct. Consider getting inspiration from the textbook in Section 2.l: the author shows that the Insert Sort algorithm is correct using loop invariants. This should help you with this exercise. l) (2 points) Express the property that Sort-Array (A) must satisfy to be correct: 2) (4 points) Can you find some loop invariants for the outer for loop? List these invariants (even if they are not that helpful for our ultimate proof of correctness of Sort-Array) 3) (9 points) Propose a loop invariant for the outer loop that is the closest to our ultimate objective: Sort-Array is correct 4) Use the three steps: a. (4 points) Initialization b. (10 points) Maintenance c. (6 points)Termination