Editing Goodstein's theorem (section)

== Sequence length as a function of the starting value ==

The '''Goodstein function''', <math>\mathcal{G}: \mathbb{N} \to \mathbb{N} </math>, is defined such that <math>\mathcal{G}(n)</math> is the length of the Goodstein sequence that starts with ''n''.  (This is a [[total function]] since every Goodstein sequence terminates.)  The extremely high growth rate of <math>\mathcal{G}</math> can be calibrated by relating it to various standard ordinal-indexed hierarchies of functions, such as the functions <math>H_\alpha</math> in the [[Hardy hierarchy]], and the functions <math>f_\alpha</math> in the [[fast-growing hierarchy]] of Löb and Wainer:

* Kirby and Paris (1982) proved that
:<math>\mathcal{G}</math> has approximately the same growth-rate as <math>H_{\epsilon_0}</math> (which is the same as that of <math>f_{\epsilon_0}</math>); more precisely, <math>\mathcal{G}</math> dominates <math>H_\alpha</math> for every <math>\alpha < \epsilon_0</math>, and <math>H_{\epsilon_0}</math> dominates <math>\mathcal{G}\,\!.</math>
:(For any two functions <math>f, g: \mathbb{N} \to \mathbb{N} </math>, <math>f</math> is said to dominate <math>g</math> if <math>f(n) > g(n)</math> for all sufficiently large <math>n</math>.)

* Cichon (1983) showed that
:<math> \mathcal{G}(n) = H_{R_2^\omega(n+1)}(1) - 1, </math>
:where <math>R_2^\omega(n)</math> is the result of putting ''n'' in hereditary base-2 notation and then replacing all 2s with ω (as was done in the proof of Goodstein's theorem).

* Caicedo (2007) showed that if <math> n = 2^{m_1} + 2^{m_2} + \cdots + 2^{m_k} </math> with <math> m_1 > m_2 > \cdots > m_k, </math> then
:<math> \mathcal{G}(n) = f_{R_2^\omega(m_1)}(f_{R_2^\omega(m_2)}(\cdots(f_{R_2^\omega(m_k)}(3))\cdots)) - 2</math>.

Some examples:

{| class="wikitable" border="1"
|-
! colspan=3 | n
! colspan=3 | <math>\mathcal{G}(n)</math> 
|-
| 1
| <math>2^0</math>
| <math>2 - 1</math>
| <math>H_\omega(1) - 1</math>
| <math>f_0(3) - 2</math>
| 2
|-
| 2
| <math>2^1</math>
| <math>2^1 + 1 - 1</math>
| <math>H_{\omega + 1}(1) - 1</math>
| <math>f_1(3) - 2</math>
| 4
|-
| 3
| <math>2^1 + 2^0</math>
| <math>2^2 - 1</math>
| <math>H_{\omega^\omega}(1) - 1</math>
| <math>f_1(f_0(3)) - 2</math>
| 6
|-
| 4
| <math>2^2</math>
| <math>2^2 + 1 - 1</math>
| <math>H_{\omega^\omega + 1}(1) - 1</math>
| <math>f_\omega(3) - 2</math>
| 3·2<sup>402653211</sup> − 2 ≈ 6.895080803×10<sup>121210694</sup>
|-
| 5
| <math>2^2 + 2^0</math>
| <math>2^2 + 2 - 1</math>
| <math>H_{\omega^\omega + \omega}(1) - 1</math>
| <math>f_\omega(f_0(3)) - 2</math>
| > [[Ackermann function|''A'']](4,4) > 10<sup>10<sup>10<sup>19727</sup></sup></sup>
|-
| 6
| <math>2^2 + 2^1</math>
| <math>2^2 + 2 + 1 - 1</math>
| <math>H_{\omega^\omega + \omega + 1}(1) - 1</math>
| <math>f_\omega(f_1(3)) - 2</math>
|  > ''A''(6,6)
|-
| 7
| <math>2^2 + 2^1 + 2^0</math>
| <math>2^{2 + 1} - 1</math>
| <math>H_{\omega^{\omega + 1}}(1) - 1</math>
| <math>f_\omega(f_1(f_0(3))) - 2</math>
|  > ''A''(8,8)
|-
| 8
| <math>2^{2 + 1}</math>
| <math>2^{2 + 1} + 1 - 1</math>
| <math>H_{\omega^{\omega + 1} + 1}(1) - 1</math>
| <math>f_{\omega + 1}(3) - 2</math>
|  > ''A''<sup>3</sup>(3,3) = ''A''(''A''(61, 61), ''A''(61, 61))
|-
| colspan=6 align=center | <math>\vdots</math>
|-
| 12
| <math>2^{2 + 1} + 2^2</math>
| <math>2^{2 + 1} + 2^2 + 1 - 1</math>
| <math>H_{\omega^{\omega + 1} + \omega^\omega + 1}(1) - 1</math>
| <math>f_{\omega + 1}(f_\omega(3)) - 2</math>
|  >  ''f''<sub>ω+1</sub>(64) > [[Graham's number]]
|-
| colspan=6 align=center | <math>\vdots</math>
|-
| 19
| <math>2^{2^2} + 2^1 + 2^0</math>
| <math>2^{2^2} + 2^2 - 1</math>
| <math>H_{\omega^{\omega^\omega} + \omega^\omega}(1) - 1</math>
| <math>f_{\omega^\omega}(f_1(f_0(3))) - 2</math>
| 
|-
|}
(For [[Ackermann function]] and [[Graham's number]] bounds see [[fast-growing hierarchy#Functions in fast-growing hierarchies]].)