Using the Well-Ordering Principle to prove that all integers less than $2^{m+1}$ can be represented by $m$ bits.

Question

Actually, the problem statement I am working with doesn't specify it's about binary numbers at all, and the problem reads as such:

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 constants 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 is at least $2^m$.

Which, well, reads to me like coded language for computer science people that any integer less than $2^{m+1}$ can be represented by an $m$-bit binary number.

So I take the provided hint under advisement and demonstrate the case that we are targeting at least $2^m$ dollars, which is easy:

If the target dollar amount is at least $2^m$, then assume there is an $m_0$ such that there is no combination of envelopes that add to $2^{m_0}$, and that $m_0$ is the smallest number with this property via the Well-Ordering Principle. Since $m_0$ is the smallest number for which this applies, there is a combination of envelopes that adds $2^{m_0-1}$ = $2^{m_0}/2$, which can be achieved with a single envelope.

However, since $m_0$ is less than $m+1$ by hypothesis, there is also an envelope twice as large as $2^{m_0-1}$, which is equal to $2^{m_0}$. Therefore, $2^{m_0}$ is representable by a combination of envelopes (and, in fact a single envelope).

I attempt to show the case where the target number of dollars is less than $2^m$ by sub-cases but I'm getting stuck.

Say, for the sake of contradiction, there is some number $n_0$ that cannot be represented by a combination of envelopes, and that this number is the smallest possible counterexample by the Well Ordering Principle. $n_0=1$ can be represented, so $n_0>1$. $n_0-1$ can then be represented with the following polynomial:

$n-1=\sum_{i=0}^{m}2^i a_i$, where $a_i$ is either $0$ or $1$.

If $n-1$ is even:

$n-1 = 2^{m}a_m + 2^{m-1}a_{m-1} + ... + 2^2a_2 + 2a_1 + a_0$

Which, if $a_0 = 0$, is an even number on the right hand side. But then, adding $1$ to both sides:

$n = 2^{m}a_m + 2^{m-1}a_{m-1} + ... + 2^2a_2 + 2a_1 + 1$

Which demonstrates that $n$ can be represented as a combination of envelopes.

I think this is sound so far, but I'm having trouble with the case where $n-1$ is odd. My computer science brain just wants to say it works like a ripple carry adder but I can't think of how to express that argument mathematically. Or perhaps there's a more elegant way to express the argument in the first place that I'm not seeing.

Answer 1

$P(m)$: For any nonnegative integer less than $2^{m+1}$, there is a selection of
$\quad\quad\;$ envelopes whose constants add up to exactly that number of dollars.

Let $S = \{m : m \in N$ and $P(m)$ is false $\}$

If $S$ is not empty, by W.O.P, $S$ has a least element $m_0$
Since $m_0$ is the least element of $S$, $m_0 - 1$ is not in $S$
So, $P(m_0 - 1)$ is true and there is a selection from envelopes $0, 1, ..., (m_0 - 1)$ that sum to $t$ for $0 \le t < 2^{m_0}$

Now, suppose we have envelopes $0, 1, ..., (m_0 - 1), m_0$
By selecting envelope $m_0$ and then selecting from envelopes $0, 1, ..., (m_0 - 1)$ there is a selection that sums to $t$ for $2^{m_0} + 0 \le t < 2^{m_0} + 2^{m_0}$ or $2^{m_0} \le t < 2^{m_0+1}$

This means that with $m_0$ envelopes, there is a selection that sums to $t$ for $0\le t < 2^{m_0+1}$
This means $P(m_0)$ is true which is a contradiction that $m_0$ is the least element of $S$.
So, $S$ must be empty and $P(m)$ must be true for all $m \in N$