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

Hercuflea

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[itex]^{0}[/itex] = 1, 2[itex]^{1}[/itex] = 2, 2[itex]^{2}[/itex]= 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

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

3. The attempt at a solution

P(n): every integer n[itex]\geq[/itex]1 can be written as a sum of distinct powers of 2.

Basis step: clearly P(1) = 1 = 2[itex]^{0}[/itex]
1 = 1

Inductive Step: Assume for some k[itex]\in[/itex]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+1 is even:
Clearly if k = 2[itex]^{j}[/itex] by the inductive hypothesis, then k+1 = 2[itex]^{j}[/itex] + 2[itex]^{0}[/itex]

I dont 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[itex]^{j}[/itex] + 2[itex]^{m}[/itex] + 2[itex]^{p}[/itex] + ...?

clamtrox

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
[tex] k = 2^a + 2^b + 2^c + ... [/tex]
where a, b, c, ... > 0. Then the unique representation for k+1 is just
[tex] k+1 = 2^0 + k [/tex]

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

Hercuflea

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

clamtrox

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[itex]^{a}[/itex] + 2[itex]^{b}[/itex] + 2[itex]^{c}[/itex] + ....

a, b, c, ...[itex]\geq[/itex]0

Then k + 1 = k + 2[itex]^{0}[/itex]
k + 1 = k + 1

Case 2: k is odd

So k = 2[itex]^{0}[/itex] + 2[itex]^{a}[/itex] + 2[itex]^{b}[/itex] + 2[itex]^{c}[/itex] +...

Where a, b, c, ...[itex]\geq[/itex]0

So k+1 = 2[itex]^{0}[/itex] + 2[itex]^{0}[/itex] + 2[itex]^{a}[/itex] + 2[itex]^{b}[/itex] + 2[itex]^{c}[/itex]

k + 1 = 2[itex]^{0}[/itex](1+1) + 2[itex]^{a}[/itex] + 2[itex]^{b}[/itex] + 2[itex]^{c}[/itex]

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=[itex]\sum_{i=0}^{m}2^{f_i(k)}, f_i(x)=0,1[/itex] let [itex] n-1=\sum_{i=0}^{m}2^{f_i(n-1)}[/itex], then [itex] 2*(n-1)=\sum_{i=0}^{m}2^{f_i(n-1)+1}[/itex]
from there add 2 to both sides, and divide by 2 (made possible since 2n is guaranteed even).

clamtrox

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)


That's a very cute way of doing it