For questions about Goodstein sequences and Goodstein's Theorem.

Given natural numbers $n$ and $b$, we can uniquely write $n$ as

$$n = a_kb^k + a_{k-1}b^{k-1} + \dots + a_1b + a_0$$

where $0 \leq a_0, \dots, a_k < b$; this is known as the base $b$ expansion of $n$. For example, with $n = 521$ and $b = 2$, we have

$$41 = 2^5 + 2^3 + 1.$$

We can further expand the exponents of the powers of $b$ in their base $b$ expansions, and continue with whatever powers arise from it; this is known as the hereditary base $b$ expansion of $n$. For example, with $n = 41$ and $b = 2$, we have

$$41 = 2^5 + 2^3 + 1 = 2^{2^2 + 1} + 2^{2 + 1} + 1.$$

The Goodstein sequence associated to $n$, denoted $G(n, i)$, is defined inductively, with first term $G(n, 1) = n$. If $G(n, i-1) = 0$, then $G(n, i) = 0$. If $G(n, i-1) > 0$, then $G(n, i)$ is obtained by taking the hereditary base $i$ expansion of $G(n, i-1)$, replacing each occurence of the base $i$ by $i + 1$, and then subtracting one from the result.

For example, the Goodstein sequence associated to $41$ begins

\begin{align*} G(41, 1) &= 2^{2^2 + 1} + 2^{2 + 1} + 1\\\ &= 41\\\ & \\\ G(41, 2) &= 3^{3^3 + 1} + 3^{3 + 1} + 1 - 1\\\ &= 3^{3^3 + 1} + 3^{3 + 1}\\\ &= 59130\\\ & \\\ G(41, 3) &= 4^{4^4 + 1} + 4^{4 + 1} - 1\\\ &= 4^{4^4 + 1} + 3\times 4^4 + 3\times 4^3 + 3\times 4^2 + 3\times 4 + 3\\\ &\approx 5.36\times 10^{154} \\\ & \\\ G(41, 4) &= 5^{5^5 + 1} + 3\times 5^5 + 3\times 5^3 + 3\times 5^2 + 3\times 5 + 3 - 1\\\ &= 5^{5^5 + 1} + 3\times 5^5 + 3\times 5^3 + 3\times 5^2 + 3\times 5 + 2\\\ &\approx 9.56\times 10^{2184}. \end{align*}

As the example above illustrates, Goodstein sequences tend to increase incredibly rapidly. However, Goodstein proved the following theorem.

Goodstein's Theorem: Every Goodstein sequence is eventually zero.

Kirby and Paris showed that this theorem cannot be proved in Peano arithmetic.