Question

Prove that the algorithm you devised in Exercise 17 is correct.

Short answer

The recursive algorithm is proved.

Step-by-step solution

Consider the recursive algorithm

The recursive algorithm is,

procedure product (x,y : nonnegative integers)

return 0

else if

y is even then

return 2. product (x, y / 2)

else return 2. prodcut (x, (y - 1) / 2) + x

 Step 2: Prove that the algorithm obtained in Exercise 17 is correct

This can be proved by Strong Induction.

Take y = 0.

The algorithm returns 0, while the product of a nonnegative integer x and 0 is x . 0 = 0 . Thus, the algorithm is correct for the basis step.

Assume that the algorithm is correct for all nonnegative integers up to k with k > 0 .

product (x, i) = x. i (when i < k)

It is required to prove that the algorithm is also correct for k + 1.

$\begin{array}{r}\mathrm{k}+1\text{even product}(\mathrm{x},\mathrm{k}+1)=2\cdot \mathrm{product}(\mathrm{x},(\mathrm{k}+1)/2)\\ =2\cdot \mathrm{x}\cdot \frac{(\mathrm{k}+1)}{2}\\ =\mathrm{x}\cdot (\mathrm{k}+1)\end{array}$

And,

$\begin{array}{r}\mathrm{k}+1\text{odd product}(\mathrm{x},\mathrm{k}+1)=2\cdot \mathrm{product}(\mathrm{x},[(\mathrm{k}+1)/2\left]\right)+\mathrm{x}\\ =2\cdot \mathrm{x}\cdot \frac{\mathrm{k}}{2}+\mathrm{x}\\ =\mathrm{x}\cdot \mathrm{k}+\mathrm{x}\\ =\mathrm{x}\cdot (\mathrm{k}+1)\end{array}$

It is observed that the algorithm gives the product and thus the algorithm is correct for the nonnegative integer k + 1.

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