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$\geq$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$\in$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$^{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, ...$\geq$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, ...$\geq$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?

 

[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