Problem:
The increasing sequence consists of all those positive integers which are powers of or sums of distinct powers of . Find the term of this sequence (where is the term, is the term, and so on).
Solution:
If we use only the first six non-negative integral powers of , namely and , then we can form on1y terms, since
Consequently, the next highest power of , namely , is also needed.
After the first terms of the sequence the next largest ones will have but not as a summand. There are of these, since , bringing the total number of terms to . Since we need the term, we must next include and omit . Doing so, we find that the terms are: and .
Note that a positive integer is a term of this sequence if and only if its base representation consists only of 's and 's. Therefore, we can set up a one-to-one correspondence between the positive integers and the terms of this sequence by representing both with binary digits ('s and 's), first in base and then in base :
This is a correspondence between the two sequences in the order given, that is, the -th positive integer is made to correspond to the -th sum (in increasing order) of distinct powers of . This is because, when the binary numbers are written in increasing order, they are still in increasing order when interpreted in any other base. (If you can explain why this is true when interpreted in base , you shou1d be able to explain it in base as well.)
Therefore, to find the term of the sequence, we need only look at the line of the above correspondence:
The problems on this page are the property of the MAA's American Mathematics Competitions