Problem
(From Mathematics for Computer Science (Lehman, Leighton, Meyers), Prob. 2.6)
You are given a series of envelopes, respectively containing 1, 2, 4, ..., $2^m$ dollars. Define
Property m: For any nonnegative integer less than $2^{m+1}$, there is a selection of envelopes whose contents add up to exactly that number of dollars.
Use the Well Ordering Principle (WOP) to prove that Property m holds for all nonnegative integers m.
Hint: Consider two cases: first, when the target number of dollars is less than $2^m$ and second, when the target number is at least $2^m$.
Solution attempt
Let's refer to Property m as $P(m)$ to make things simpler.
Let $C$ be the following set:
$C = \{ m \mid \text{P(m) doesn't hold for } m\}$
Then, by the WOP, there is a smallest integer $m_0$ in $C$.
$P(m)$ holds for m = 0, since any nonnegative integer less than $2^{0+1} = 2$ can be represented with a selection of envelopes (the integer $0$ can be represented by a selection of no envelopes, and the integer $1$ can be represented with the envelope containing $1$). So, $m_0 > 0$.
Also, $P(m_0-1)$ holds (since $m_0-1 < m_0$), which means that all nonnegative integers less than $2^{m_0}$ can be represented by a selection of envelopes that contain up to $2^{m_0-1}$.
Since $P(m_0)$ is false, this means that there is a nonnegative integer $c$ less than $2^{m_0 + 1}$ such that $c$ can't be obtained by a selection of the envelopes $1$, $2$, $4$, ..., $2^{m_0}$.
From the above paragraph, we know that $c < 2^{m_0+1}$, and, from the fact that $P(m_0-1)$ holds, we know that $c \geq 2^{m_0}$. So:
$2^{m_0} \leq c < 2^{m_0+1}$
To show that there is a contradiction, there are two cases:
If $c$ is even: Dividing the above inequality by 2, $2^{m_0-1} \leq c/2 < 2^{m_0}$. So, since $c/2$ is smaller than $2^{m_0}$, $P(c/2)$ holds and $c/2$ can be represented by a selection of envelopes. However, this means that $2(c/2) = c$ can also be represented as a selection of envelopes, which is a contradiction.
If $c$ is odd: Subtracting 1 from the above inequality and dividing it by 2, $2^{m_0-1} - 1/2 \leq (c - 1)/2 < 2^{m_0} - 1/2$. Since $(c - 1)/2$ is smaller than $2^{m_0}$, $P((c - 1)/2)$ holds and $(c - 1)/2$ can be represented by a selection of envelopes. However, this means that $2((c - 1)/2) + 1 = c$ can also be represented as a selection of envelopes, which is a contradiction.
So, $C$ is empty and $P(m)$ holds for all nonnegative integers $m$.
I didn't use the provided hint in my solution attempt, which makes me think that there might be something incomplete about this attempt. Is there anything missing from this proof attempt?