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:
33 in hreditary base-2 notation.

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:
The next value in the Goodstein sequence for 33
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

One thought on “Goodstein Sequences

  1. Pingback: Ars Mathematica » Blog Archive » Goodstein Revisited

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>