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

1. Jun 29, 2012

### 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$^{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

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

3. 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 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$^{j}$ + 2$^{m}$ + 2$^{p}$ + ...?

Last edited: Jun 29, 2012
2. Jun 29, 2012

### 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
$$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.

3. Jun 29, 2012

### Hercuflea

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

4. Jun 29, 2012

### clamtrox

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

5. Jun 29, 2012

### 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????

6. Jun 29, 2012

### 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).

7. Jun 29, 2012

### 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