[note: also under discussion in s.o.s. math board]
Split your inductive step into two cases, one where k+1 is odd, and one where k+1 is even.
When k+1 is even, (k+1)/2 is a natural number and is less than k, so your inductive hypothesis holds for it. Therefore
as you defined, so
I'll leave the other case to you, good luck.
So the induction hypothesis holds even when it's less than k? Are you using STRONG induction?
Also, I think the "m" may be different for each natural number n, so the labelling for the exponents for each number should be different and the number of terms may also be different for each natural number n (so we can't use the same "m" for the different natural numbers n). So can we still say ?
For uniqueness, I think this works.
Suppose that . We may assume WLOG that and so dividing by gives it is clear by assumption and what we imposed on that the right side is going to be odd iff , and since it must be odd (since the left side is one plus a series of even terms) it follows that . Thus, we may subtract from both sides to get . Now, we may repeat this procedure of dividing by the leading term and deducing that they are only of the same parity of the leading term was the same...and dividing and repeating. Thus, by induction it follows that the two sequences must be exactly the same.
OK, then if we're using strong induction, I am wondering how we can state the induction hypothesis properly?
For all 1≤n≤k,
where m≥0 and 0≤jo<j1<j2<...<jm
I think there is some problem stating the induction hypothesis this way, becuase for n=1, it may be m, but for n=2, it may be something else (note necessarily m), and etc...for n=k ?
Thanks for explaining, but I am a bit confused as I suspect there may be some typos...
Do you mean for all 1≤n≤k-1?
I don't understand howIf is even then satisfies the above and so so that . If is odd then so that . The last step was justifiable, under the imposed conditions, since was even, hence not containing any .
can possibly imply that
If you multiply the RHS by 2 and then add 1, shouldn't the exponent be j_l +1?
Thanks!
So I assume the induction hypothesis is:
For all 1≤n≤k-1,
n may be represented as the sum of powers of two.
And then we proceed to show that k can be represented as the sum of powers of two.
I believe we do need to justify why k/2 ≤ k-1 and (k-1)/2 ≤ k-1 so that we can use our induction hypothesis, right?
I tried graphing these as straight lines and it's quite clear from the graph, but how can we prove it?
I can see from the graph, but I can't PROVE e.g. k/2 ≤ k-1. (I was told that a graph is not a PROOF)
Suppose k is even, k≥2
k≥2 => k/2≥1, but we need the inequalty in the other way.
Alternatively, k≥2 => k-1≥1, but 1 is not always ≥ k/2, what else can I try?
Another way, note that the generating function of the number of ways a natural number can be written as a sum of distinct powers of 2 is:
Now if you want an "elementary" proof:
By induction, 0 clearly has a unique representation as sum of distinct powers of 2 -do not sum anything!-, now suppose it holds for all natural numbers up to .
Consider to be the greatest power of 2 less or equal than (1), clearly .
So can be represented uniquely as a sum of distinct powers of 2, furthermore, none of them can be equal to for otherwise: and so by the definition (1), which is clearly a contradiction, hence can be written as a sum of distinct powers of 2.
(and that representation has to be unique since so is the representation of - note that is always part of the representation of since otherwise a contradiction!, the rest follows naturally)