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

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.

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