Car Talk Puzzler: Dollars and Envelopes

I'm a fan of the NPR show Car Talk, which, as I have mentioned before, includes a segment known as The Puzzler.  This week's problem is of a purely mathematical nature, so, as is not the case when the subject matter is automotive, I have a chance.  Here's the puzzle:

Suppose you have a thousand 1-dollar bills and ten envelopes.  The challenge is to put the bills in the envelopes in such a way that, if someone asks for any number of dollars from one to a thousand, you can turn over exactly the sum requested by handing out  envelopes.

I was in the car when I heard it, and the only thing I could figure out before I got home is that it's probably advisable to worry first about being able to comply with small requests.  After all, someone might ask for just a dollar, in which case you need (obviously!) one envelope with a single dollar bill in it.  And if they ask for two dollars, you need either an envelope with two dollars in it, or two envelopes with one dollar.  At first, it seems like it's going to be pretty hard to comply with these small requests and those in the 800- or 900-dollar range. 

But at home, with the aid of pencil and paper, it soon became apparent that you can make use of the fact that the expression 2ⁿ gets quite large quite fast as n rises through the smallest integers.  I had my 1-dollar and 2-dollar envelopes.  I surmised that a 3-dollar one was unnecessary, since 1 + 2 = 3.  But a 4-dollar envelope is necessary.  The next one that's necessary has eight dollars.  Perhaps this is enough to spot a pattern, since at this point the number of bills in the four used envelopes is given by 2⁰, 2¹, 2², and 2³, respectively.  In the fifth envelope, you need 2⁴, or sixteen, dollar bills.  And you proceed in this fashion until, in the ninth envelope, you put 2⁸, or 256, dollar bills.  Now put all the remaining bills--489 of them--in the tenth envelope.  It's pretty clear that you can now comply with any request, right?  The first nine envelopes cover any request up to $511.  All ten envelopes cover the request for all 1000 dollars.  And if the ten envelopes contain a total of $1000, and the first nine can be made to yield any sum from 1 to 511, it is clear that, to cover the numbers from 512 to 999, you can subtract an envelope, or some combination of them, from all ten to get the required amount.