Goodstein Sequences
The Goodstein sequence G(m) of a number m is a sequence of natural numbers. The first element in the sequence G(m) is m itself. To get the next element, write m in hereditary base 2 notation, change all the 2s to 3s, and then subtract 1 from the result; this is the second element of G(m). To get the third element of G(m), write the second element in hereditary base 3 notation, change all 3s to 4s, and subtract 1 again. Continue until the result is zero, at which point the sequence terminates.
Early Goodstein sequences terminate quickly. For example, G(3) terminates at the sixth step:
| Base | Hereditary notation | Value | Notes |
|---|---|---|---|
| 2 | 3 | Write 3 in base 2 notation | |
| 3 | 3 | Switch the 2 to a 3, then subtract 1 | |
| 4 | 3 | Switch the 3 to a 4, then subtract 1. Now there are no more 4s left | |
| 5 | 2 | No 4s left to switch to 5s. Just subtract 1 | |
| 6 | 1 | ||
| 7 | 0 |
Later Goodstein sequences increase for a very large number of steps. For example, G(4) starts as follows:
| Hereditary notation | Value |
|---|---|
| 4 | |
| 26 | |
| 41 | |
| 60 | |
| 83 | |
| 109 | |
| 253 | |
| 299 | |
Elements of G(4) continue to increase for a while, but at base, they reach the maximum of, stay there for the next steps, and then begin their first and final descent.
The value 0 is reached at base (curiously, this is a generalized Woodall number: . This is also the case with all other final bases for starting values greater than 4).
However, even G(4) doesn't give a good idea of just how quickly the elements of a Goodstein sequence can increase. G(19) increases much more rapidly, and starts as follows:
| Hereditary notation | Value |
|---|---|
| 19 | |
| 7,625,597,484,990 | |
|
|
|
|
|
|
In spite of this rapid growth, Goodstein's theorem states that every Goodstein sequence eventually terminates at 0, no matter what the starting value is.
Read more about this topic: Goodstein's Theorem