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.
|
|
Bookmarks