Suppose the INCREMENT operation is correct for a counter with k $1$ bits. Let c be the counter after the INCREMENT operation. If c has k$+11$ bits, then the highest$-$order $1$ bit in c must be in a position to the left of the highest$-$order $1$ bit in the original counter. Therefore, the INCREMENT operation correctly flips the highest$-$order $0$ bit to $1$ and resets all higher$-$order $1$ bits to $0.$ By the induction hypothesis, the INCREMENT operation is correct for the counter with k $1$ bits, so the overall correctness follows.