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

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}$ + ...?
 PhysOrg.com science news on PhysOrg.com >> King Richard III found in 'untidy lozenge-shaped grave'>> Google Drive sports new view and scan enhancements>> Researcher admits mistakes in stem cell study

 Quote by Hercuflea 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.

 Quote by 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.
sorry, that was my first time fooling around with the superscripts. It's fixed now.

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

 Quote by Hercuflea 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
 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????
 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).

 Quote by Hercuflea 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)

 Quote by 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).
That's a very cute way of doing it