Prove by induction that every positive integer can be defined as a sum of distinct powers of 2, i.e. as a sum of the subset of the integers , and so on.
(For the inductive step, consider the case where is even and the case where it is odd.)
I found a variant online on how to prove this via contradiction, but it doesn't use the odd/even cases. I'd prefer it if I had the odd/even induction case version in case it is a requirement.