Low Level Well-Ordering Principle Proof Suppose that I have k envelopes, numbered $0,1,...,k−1$, such that envelope i contains $2^i$ dollars. Using the well-ordering principle, prove the following claim.

Claim: for any integer $0 ≤ n &lt; 2^k$, there is a set of envelopes that contain exactly n dollars between them.

How would I tackle this problem? I am stumped. I know that the well-ordering principle states that a non-empty set will always have a smallest element in the set, but I don't exactly know how to apply it to write the proof.
Call the positive integer $k$ bad if there is a set of $k$ envelopes, numbered $0$ to $k-1$, with contents as described in the question, and an integer $n\lt 2^k$, such that no subset of the envelopes contains exactly $n$ dollars between them.

We want to prove there are no bad $k$.  Suppose to the contrary that there are. Then the set $B$ of bad $k$ is non-empty. It follows that there is a smallest bad $k$.  Call it $m$.

$m$ is greater than $0$, because $m=0$ holds obviously.

So $m$ is bad, and all positive integers $\lt m$ are good.

We arrive at a contradiction by showing that $m$ is good, that is, that any number $n\lt 2^m$ of dollars can be obtained by choosing an appropriate collection of the envelopes.

Case (i), $n\lt 2^{m-1}$: Since $m-1$ is good, there is a subset of the first $m-1$ envelopes that gives sum $n$.

Case (ii), $2^{m-1}\le n\lt 2^m$. Take the contents of the biggest envelope, that is, envelope with label $m-1$, which has $2^{m-1}$ dollars. 

Then we still need an amount $a$ of dollars, where $0=2^{m-1}-2^{m-1}\le a\lt 2^m-2^{m-1}=2^{m-1}$.  Because $m-1$ is good, we can produce this amount $a$ from the first $m-1$ envelopes. Hence by adding the contents of the envelope with label $m-1$, we get our $n$ dollars.  

Remark: This is just an ordinary proof by induction, rewritten to use "well-ordering principle" language.
Let S denote the values in $\{0,1,2,…,2k−1\}$ that cannot be expressed with the envelopes. $0$ is not in $S$, because "no envelopes" has zero dollars. $S$ is well-ordered because it is a subset of the naturals; if it is nonempty it has a smallest element $s$. Hence $0,1,2,…,s−1$ can all be expressed with combinations of envelopes, but s cannot be. You need to use the combination of these two facts to get a contradiction; hence $S$ is empty and your theorem is proved.

If you need a hint for how to get that contradiction, let me know.

How do I get to a contradiction?