Q2 Proof of algorithm is correct with weak induction

• SP(x,n) // SP stands for "slow power"
• FP(x,n) // FP stands for "fast power"

These algorithms both take two parameters: a non-zero real number called x, and a natural number called n. The algorithms do not perform any error checking of the values passed to them. They are simply assumed to be correct. These algorithms both return a real number which is xn

Here is pseudocode for the algorithms:

SP(x,n) result = 1 for (i=1; i<=n; i++) result = result *x return result

FP(x,n) if n==1 return x if n is even return FP(x*x, n/2) else return x*FP(x*x,(n-1)/2)

In this question you will use strong induction to prove that the algorithm works correctly.

In other words, you will prove that for all n and for all x - {0} FP(x,n) = xⁿ

1. Predicate Function (1 mark)

Your conjecture has already been stated in symbolic form:

It is a statement of the form n P(n)

What is the predicate function P(n)?

2. Proof: Base cases (4 marks)

3. Proof: Inductive step setup (2 marks)

This is the beginning of the inductive step where you are stating the assumptions in the inductive step and what you will be proving in that step. As you do so, identify the inductive hypothesis.

4. Proof: Inductive step (14 marks)