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

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.

I would help if I could but I can only stare blankly and only slightly understand about 2% of what I just read

Well the stuff at the bottom is probably wrong but it's what I have done so far.

Your problem is a misunderstanding of induction. Don't worry about this, it's very new when you first meet it.

Firstly, your proposition doesn't have the right form. The kind of statements you try to prove by induction are statements which are somehow statements about all positive integers (or in fact any countably infinite set). Here the statement is 'all positive integers are sums of distinct powers of 2'. This can be rephrased as, '1 is a sum of distinct powers of 2, and 2 is a sum of distinct powers of 2, and 3 is a sum of distinct powers of 2, ...' and so on. These individual statements, about single numbers, are what we represent by P(1), P(2), P(3), ... . As it stands your proposition, 'P(n): every integer n≥1 can be written as a sum of distinct powers of 2', doesn't make much sense. n is supposed to be some fixed number, and P(n) represents the statement for that number; if we took n to be 5 for instance, your proposition P(5) would be 'every integer 5 ≥ 1 can be written as a sum of distinct powers of 2'. What we want is, 'P(n): n is a sum of distinct powers of 2'.

Secondly, there's a difference between strong induction and weak induction (technically you can use weak induction to prove anything that you can prove by strong induction, but that's not important here and in any case it's less messy to use strong induction). You are trying to use weak induction, where you assume that P(k-1) is true in order to prove P(k), and thus P is true for all positive integers n (given P(1)), by weak induction. Hopefully it's obvious how this works; it's always valid to assume that the previous statement is true, because you can reach it by 'building up' from 1.

Strong induction is different: again, you wish to prove P(k), but this time you can assume that all statements P(1), P(2), ... , P(k-1) are true. This is more powerful; maybe you need to know P(3) in order to prove P(5), for instance. You couldn't do it simply with weak induction. Hopefully it's again clear why this means that P(n) is true for all positive integers n; once again you 'build up' from 1, but this time you remember all of the things you have proven so far, instead of just the previous one.

Maybe you can take another shot now. Your proof for when k is odd is correct; k - 1 is even but with no odd term, so k is the same sum of distinct powers of 2 but with 1 added on. You can do this bit by weak induction. But when k is even, instead of looking at k - 1, you'll want to look at k/2, as the question suggests. Here you will be using strong induction.