Goodstein's Theorem - Hereditary Base-n Notation

Hereditary Base-n Notation

Goodstein sequences are defined in terms of a concept called "hereditary base-n notation". This notation is very similar to usual base-n positional notation, but the usual notation does not suffice for the purposes of Goodstein's theorem.

In ordinary base-n notation, where n is a natural number greater than 1, an arbitrary natural number m is written as a sum of multiples of powers of n:

where each coefficient satisfies, and . For example, in base 2,

Thus the base 2 representation of 35 is . (This expression could be written in binary notation as 100011.) Similarly, one can write 100 in base 3:

Note that the exponents themselves are not written in base-n notation. For example, the expressions above include and .

To convert a base-n representation to hereditary base n notation, first rewrite all of the exponents in base-n notation. Then rewrite any exponents inside the exponents, and continue in this way until every digit appearing in the expression is n or less.

For example, while 35 in ordinary base-2 notation is, it is written in hereditary base-2 notation as

using the fact that Similarly, 100 in hereditary base 3 notation is