If n is binary represented natural number, P(n) for some predicate P.
This is just a sample question I made.
Base case) Let n = 0. This is divisible by 2
Induction step) Let n = k is a binary represented natural number such that P(n) is true.
In this case, what should I prove? I found that if k is binary number, 2k and 2k+1 are binary number and they can cover all the binary numbers.
I think if I prove n+1 = 2k or 2k+1 is true for P, I can prove P(n+1) is true by induction. But I'm not sure how can I justify n+1 is 2k or 2k+1.