Math induction - I think i totally missed the point of it.

[Hercuflea]

Homework Statement

"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.]

Homework Equations

Assume P(k) and show that P(k)--->P(k+1)

The Attempt at a Solution

P(n): every integer n\geq1 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\inN 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+1 is even:
Clearly if k = 2^{j} by the inductive hypothesis, then k+1 = 2^{j} + 2^{0}

I don't even see why I need a case 2. Apparently I have proven this by a direct proof even though I was trying to do induction.

I just don't know how to properly set up induction word problems. I have an easier time when the conjecture is given numerically. How can I write an equation for "n can be written as the sum of powers of 2" without making a bunch of new variables, like n = 2^{j} + 2^{m} + 2^{p} + ...?

 

[clamtrox]

Case 1: k+1 is even:
Clearly if k^{}j = 2^{}j by the inductive hypothesis, then k+1 = 2^{}j + 2^{}0

What are you doing here? That doesn't seem to make much sense...

So if you have k even, then by induction there exists a representation
k = 2^a + 2^b + 2^c + ...
where a, b, c, ... > 0. Then the unique representation for k+1 is just
k+1 = 2^0 + k

Then you need to work out what happens when k is odd.

 

[Hercuflea]

What are you doing here? That doesn't seem to make much sense...

So if you have k even, then by induction there exists a representation
k = 2^a + 2^b + 2^c + ...
where a, b, c, ... > 0. Then the unique representation for k+1 is just
k+1 = 2^0 + k

Then you need to work out what happens when k is odd.

sorry, that was my first time fooling around with the superscripts. It's fixed now.

 

[clamtrox]

sorry, that was my first time fooling around with the superscripts. It's fixed now.

Yea those were messed up but your reasoning is still a bit incomplete

 

[Hercuflea]

Ok, so this is what I have so far.

Case 1: k is even

So k = 2^{a} + 2^{b} + 2^{c} + ...

a, b, c, ...\geq0

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, ...\geq0

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?

 

[tt2348]

don't worry about even or odd, instead think of it as for for k=1...n-1 we have k=\sum_{i=0}^{m}2^{f_i(k)}, f_i(x)=0,1 let n-1=\sum_{i=0}^{m}2^{f_i(n-1)}, then 2*(n-1)=\sum_{i=0}^{m}2^{f_i(n-1)+1}
from there add 2 to both sides, and divide by 2 (made possible since 2n is guaranteed even).

 

[clamtrox]

k + 1 = 2^{0}(1+1) + 2^{a} + 2^{b} + 2^{c}

k+1 = k + 2?

No, you want to show that you can write k+1 = 2^a + 2^b + 2^c + ..., not that k+1=k+1 (that is obvious)

don't worry about even or odd, instead think of it as for for k=1...n-1 we have k=\sum_{i=0}^{m}2^{f_i(k)}, f_i(x)=0,1 let n-1=\sum_{i=0}^{m}2^{f_i(n-1)}, then 2*(n-1)=\sum_{i=0}^{m}2^{f_i(n-1)+1}
from there add 2 to both sides, and divide by 2 (made possible since 2n is guaranteed even).

That's a very cute way of doing it