Question

Prove that the recursive algorithm for finding the concatenation of i copies of a bit string that you gave in Exercise 38 is correct.

Short answer

It has been proved that recursive algorithm is correct.

Step-by-step solution

Given that

Given the recursive algorithm for finding the concatenation of i copies of a bit string is as:

procedure power(w: bit string, i: nonnegative integer)

if i = 0 then return $\lambda$

else return wconcatenated with power (w, i - 1)

Prove the correctness of algorithm

If i = 0, then by definition$w^i$ is no copies of w, so the output string is correct.

If the algorithm correctly returns the $i^{th}$power of w, then it correctly returns the${\left(i+1\right)}^{st}$ power of w by concatenating one more copy of w.

Hence, the algorithm is correct