This can be done with strong (also called course-of-value) induction, where P(k + 1) is proved not only from P(k) but from P(0), ..., P(k). (By the way, the principle of strong induction is not in fact stronger; it can be expressed using ordinary induction by changing the statement P.)

So, if k + 1 is even, represent (k + 1) / 2, which is (usually) < k, and add one to every power. If k + 1 is odd, then representation of k does not include 2^0, so add it.