Well Ordering Principle Question

Question

You are given a series of envelopes, respectively containing 1, 2, 4, , , , , 2^m dollars.
Definition:
Property 1: 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 1 holds for all
nonnegative integers m.
Hint: Consider two cases:

1 When the target number of dollars is less than 2^m
2.When the target is at least 2^m

Answer 1

It is actually a proof by induction and the process, though not a rigorous proof,

is essentially the same as  changing a positive integer value to binary.

The envelopes are simply powers of 2 in disguise.

 

Principal of Math Induction is based on the well ordering principle anyway.

That is, there must be a starting point as to show that the statement holds

for the small(er) integral values (case 1 in your problem description).

The the induction hypothesis is used to prove that IF the statement is true for some positive integer N,

THEN it MUST necessarily hold (by deductive proof or contradiction) for N+1 (case 2 in your problem description).

Once proven, the statement holds for any positive integer.

 

As a reminder, here is how to change a positive integer to binary.

For example: 125

 

First we need powers of 2, for the first 8 bits

1 = 2^0

2 = 2^1

4 = 2^2

8 = 2^3

16 = 2^4

32 = 2^5

64 = 2^6

128 = 2^7  <--- this is larger than 125, so we don't need it and we can stop here;

                          it will be zero in the binary expansion.

 

Now we keep dividing each power of 2 in the list into the remainder.

125/128 = 0 with remainder 125

125/64 = 1 with remainder 61

61/32 = 1 with remainder 29

29/16 = 1 with remainder 13

13/8 = 1 with remainder 5

5/4 = 1 with remainder 1

1/2 = 0 with remainder 1

1/1 = 1 with remainder 0

 

So the binary bit string that represent 125 is 01111101

 

This discussion will serve as the preliminary steps for

the proof by induction, as clearly the first several positive

integers can be written with powers of 2 in this manner.

 

Induction Hypothesis:   The first 2^m positive integers can be

                                    written as the sum of powers of 2.

 

It remains to show that 2^(m+1) can be written as the sum of powers of 2

GIVEN the induction hypothesis holds.

 

Proof:

 

 

Let the finite series sequence 2^m = SUM (B_i*2^i)  be the sum of powers of 2 for 2^m per induction hypothesis,

   where i=0,1,2,.....,k  for positive integer k and B_i = {0,1}.

  That is B_i is simply the bit that represents that particular power of 2. If one (1) the bit is on, if zero (0) the bit is off

   as described above. Moreover, if B_i is zero then that term does not contribute to the sum in the binary expansion.

 

 Specifically 2^m = B_0 * 2^0 + B_1 * 2^1 + B_2 * 2^2 + B_3 * 2^3  + ....  + B_(k-1) * 2 ^ (k-1) +  B_k * 2^k,

           again where B_i is either zero or one

 

 Recall the property of exponents, which says when multiplying monomials

 of the same base, the exponents are added. That is  2 ^ X * 2 = 2 ^ (X+1) for integer X.

With that reminder being said, we multiply both sides by 2.

 

Then 2^(m+1) appears on the left as needed.

  Multiplying each term in the binary expantions on the right by 2 simply increases the exponent by 1.

 

The expansion is now:

  0 * 2^0 +  B_0 * 2^1 + B_1 * 2^2 + B_2 * 2^3 + B_3 * 2^4 + .... + B_(k-1) * 2^k + B_k * 2^(k+1)

 

with the same set of B_i.

 

Notice the term 0 * 2^0 = 0 is added to the beginning of the expansion which does not change the value.

 This basically proves that when doubling the integers, the bits in the binary expansion shift one place to the

  left <--- with a zero filling in the last spot.

 

 This concludes the proof because the set of B_i ( which represents the envelopes) has not changed.

We have shown that 2^(m+1) can be written as a sum of powers of 2.

 

Lets double our previous example:

  2 x 125 = 250.

 

Changing 250 to binary, 250 = 128 + 64 + 32 + 16 + 8 + 2 

   So the binary expansion of 250 = 1 1 1 1 1 0 1 0 

 

 For your convenience the binary expansion for 125 is/was 01111101

Notice the bits shifted to the left one place, with zero filler on the right