# Goodstein Sequences

Goodstein sequences are integer sequences with a very surprising property.

Start with any number. Rewrite the number as a sum of powers of 2. In turn, rewrite the exponents as powers of 2, then the exponents of exponents, etc. For example, we’d write 33 as:
.

To compute the next value in the sequence, replace every 2 with a 3, and subtract 1. The next value in the Goodstein sequence for 33 is:

which is equal to 22876792454961.

For the next step, we replace the 3s with 4s and subtract 1, etc. This sequence continues to increase very rapidly, right?

Wrong. Goodstein proved that for any starting value, the sequence eventually goes to zero. Even more surprisingly, the proof relies on properties of infinite ordinal arithmetic. The theorem cannot have an appreciably more elementary proof: the result is independent of the Peano axioms for arithmetic.

A minicourse on Goodstein sequences and some related examples can be found at this online course: Fast-Growing Functions and Unprovable Theorems