A Goldstein sequence may be defined in the following way:
Given any positive integer k, let . Now, write k as a sum over its binary expansion. For example, for , we have . Then write each exponents in the binary expansion as a binary expansions as well. Continuing with the previous example:
Now, define to be the number obtained in from this expansion for by first replacing all the 2s with 3s, and then subtracting 1 from the result. So, for our example,
We generalize this recurrence: given each , write it in its base-k+1 representation, and write each of the exponents in their base-k+1 representation. Then we define by replacing all instances of k+1 in the expanded expression with k+2, and subtracting 1 from the result. For example, for :
This is well-defined because the base expansion is guaranteed to be unique, and we will never encounter any b as a coefficient in the base-b expansion.
Intuitively, it seems that the sequence is increasing very quickly: for our example, in the first two steps the sequence goes from 10 to 1026, and each step adds to both the base and the exponent. One might expect that the sequence will proceed to infinity.
However, it can be shown that the limit of every such sequence is 0. The secret here is the fact that we subtract 1 in each step. This surprising result can be proven by defining a 'size function' σ which, given any in its expanded form, maps the base k+1 to ω (the first transfinite ordinal) but leaves the rest of the expression intact. For example:
When we compare with , we see that the rule for transforming with by replacing k+1 does not change the value of , because the k+1 is mapped to ω. However, we can see from the above example that the fact that we are subtracting 1 does affect σ: the ordinal value of is decreased by 1 with each step.