Suppose that we have a binary counter with k bits, where each bit is stored in a array A[0..k - 1]. The operation Increment(A) increments the counter by adding 1 to the content of the counter modulo 2k . The cost of this operation is proportial the number of bits that need to be inspected, so it is at most O(k).
a) Prove that if a sequence of n increment operations is applied to a counter that is initially zero, then at most 2n bits are flipped, by counting the number of bit flips. [Hint: Note that A[0] flips every time, A[1] flips every other time, etc.]
b) Use now the accounting method to prove that at most 2n bits are flipped, when a sequence of n increment operations is executed on a counter that is initially zero.