function pown k 1 c 0 while c n do k 2 k c c 1 end wh

function pow(n)

k = 1 c = 0

while c < n do

k = 2 · k

c = c + 1 end while

return k

end function

(a) Consider the following loop invariant for the while loop: At the beginning of the while loop, we have k = 2^c . Prove that the invariant holds by induction.

Solution

At the beginning of loop i.e., when c = 0; K = 2^c = 2^0 = 1.

After first iteration, c is incremented to one and its value becomes 1 and value of k is k = 2*1 (previous value of k) = 2 which is 2^1(value of c).

After second iteration, c is incremented to one and its value becomes 2 and value of k is k = 2*2 (previous value of k) = 4 which is 2^2(value of c).

After third iteration, c is incremented to one and its value becomes 3 and value of k is k = 2*3 (previous value of k) = 3 which is 2^3(value of c).

Similarly, c is incremented by one at each iteration and after n-2 iteration, value of c will be updated to n-2 and value of k will be 2 *(2^(n-3) = 2^(n-2).

Hence, by above statements we can conclude that k=2^c i.e., loop-invariant holds.