# Goldstein sequence

In mathematics, Goldstein sequences are an interesting example of the power of ordinal arithmetic.

## Definition

A Goldstein sequence $\{a_{n}\}_{{n=1}}^{\infty }$ may be defined in the following way:

Given any positive integer k, let $a_{1}=k$. Now, write k as a sum over its binary expansion. For example, for $k=10$, we have $a_{1}=10=2^{3}+2^{1}$. Then write each exponents in the binary expansion as a binary expansions as well. Continuing with the previous example:

$a_{1}=2^{3}+2^{1}=2^{{2^{1}+1}}+2^{1}$

Now, define $a_{2}$ to be the number obtained in from this expansion for $a_{1}$ by first replacing all the 2s with 3s, and then subtracting 1 from the result. So, for our example,

$a_{2}=(3^{{3^{1}+1}}+3^{1})-1=83$

We generalize this recurrence: given each $a_{k}$, write it in its base-k+1 representation, and write each of the exponents in their base-k+1 representation. Then we define $a_{{k+1}}$ by replacing all instances of k+1 in the expanded expression with k+2, and subtracting 1 from the result. For example, for $a_{3}$:

$a_{2}=83=(3^{{3^{1}+1}}+2$ $a_{3}=(4^{{4^{1}+1}}+2)-1=1026$

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.

## Properties

Intuitively, it seems that the sequence $a_{n}$ 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 $a_{k}$ in its expanded form, maps the base k+1 to ω (the first transfinite ordinal) but leaves the rest of the expression intact. For example:

$\sigma (a_{1})=\sigma (2^{{2^{1}+1}}+2^{1}+1)=\omega ^{{\omega ^{1}+1}}+\omega ^{1}$
$\sigma (a_{2})=\sigma (3^{{3^{1}+1}}+2)=\omega ^{{\omega ^{1}+1}}+2$
$\sigma (a_{3})=\sigma (4^{{4^{1}+1}}+1)=\omega ^{{\omega ^{1}+1}}+1$
$\sigma (a_{4})=\sigma (5^{{5^{1}+1}})=\omega ^{{\omega ^{1}+1}}$

When we compare $\sigma (a_{k})$ with $\sigma (a_{{k+1}})$, we see that the rule for transforming $a_{k}$ with $a_{{k+1}}$ by replacing k+1 does not change the value of $\sigma$, 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 $\sigma (a_{n})$ is decreased by 1 with each step.

Since the nonnegative integers are totally ordered, and the value of $\sigma (a_{n})$ is a infinite strictly decreasing sequence with respect to this order, then its limit is the lower bound of the set, namely 0.