Help: I passed Calc 1-3 with flying colors, now I'm utterly failing discrete math.

[Hercuflea]

So I just can't get the hang of discrete math. Here is a proof I have been working on, but haven't gotten far with. 1. The problem statement, all variables and given/known data "Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 2^0 = 1, 2^1 = 2, 2^2= 4, and so on. [Hint: for the inductive step, separately consider the case where k+1 is even and where it is odd. When it is even, note that (k+1)/2 is an integer.] 2. Relevant equations For strong induction, Assume P(1) and P(2) and P(3) and...and P(k) and show that these all ---> P(k+1) 3. The attempt at a solution P(n): every integer n≥1 can be written as a sum of distinct powers of 2. Basis step: clearly P(1) = 1 = 2^0 1 = 1 Inductive Step: Assume for some k∈N that k can be written as distinct powers of 2. Show that k+1 can be written as distinct powers of 2. Case 1: k is even So k = 2^a + 2^b + 2^c + .... a, b, c, ...≥0 Then k + 1 = k + 2^0 k + 1 = k + 1 Case 2: k is odd So k = 2^0 + 2^a + 2^b + 2^c +... Where a, b, c, ...≥0 So k+1 = 2^0 + 2^0 + 2^a + 2^b + 2^c k + 1 = 2^0(1+1) + 2^a + 2^b + 2^c k+1 = k + 2???? How do I set this equation up properly? I can't seem to find a relationship that works out.