function pow(n)

k = 1 c = 0

while c < n do

k = 2 k

c = c + 1

end while

return k

end function

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.