Question

Prove that the recursive algorithm that you found in Exercise 7 is correct.

Short answer

It is proved by induction that the recursive algorithm is correct.

Step-by-step solution

Consider the recursive algorithm

The recursive algorithm is,

procedure product (n ; positive integer , x : integer)

if n = 1 then return x

else return product (n - 1, x) + x

Prove that the algorithm obtained in Exercise 7 is correct

This can be proved by Induction.

For the basis step, if n = 1, then nx = x. Therefore, the algorithm correctly return x.

For the inductive step, assume that the algorithm correctly determine kx. It is required to prove that the algorithm is also correct for (k + 1) x .

Using the recursion, it computes the product of k + 1 - 1 = k and x, and then add . As per the inductive hypothesis, it computes that product correctly, so the answer returned is kx + x = (k + 1) x, which is the correct answer.

Hence, by the principle of induction, the recursive algorithm is correct.