Editing Goodstein's theorem (section)

== Goodstein sequences ==

The '''Goodstein sequence'''  <math>G_m</math> of a number ''m'' is a sequence of natural numbers. The first element in the sequence <math>G_m</math> is ''m'' itself. To get the second, <math>G_m (2)</math>, write ''m'' in hereditary base-2 notation, change all the 2s to 3s, and then subtract 1 from the result. In general, the {{nowrap|1 + ''n''th}} term, <math>G_m (n+1)</math>, of the Goodstein sequence of ''m'' is as follows:
* Take the hereditary base-{{nowrap|''n'' + 1}} representation of <math>G_m (n)</math>.
* Replace each occurrence of the base-{{nowrap|''n'' + 1}} with {{nowrap|''n'' + 2}}.
* Subtract one. (Note that the next term depends both on the previous term and on the index ''n''.)
* Continue until the result is zero, at which point the sequence terminates.

Early Goodstein sequences terminate quickly. For example, <math>G_3</math> terminates at the 6th step:

{| class="wikitable" border="1"
|-
! Base !! Hereditary notation !! Value !! Notes
|-
|    2 || <math> 2^1 + 1 </math>           || 3 || Write 3 in base-2 notation
|-
|    3 || <math> 3^1 + 1 - 1 = 3^1 </math> || 3 || Switch the 2 to a 3, then subtract 1
|-
|    4 || <math> 4^1 - 1 = 3 </math>       || 3 || Switch the 3 to a 4, then subtract 1. Now there are no more 4's left
|-
|    5 || <math> 3 - 1 = 2 </math>         || 2 || No 4's left to switch to 5's. Just subtract 1
|-
|    6 || <math> 2 - 1 = 1 </math>         || 1 || No 5's left to switch to 6's. Just subtract 1
|-
|    7 || <math> 1 - 1 = 0 </math>         || 0 || No 6's left to switch to 7's. Just subtract 1
|}

Later Goodstein sequences increase for a very large number of steps. For example, <math>G_4</math> {{OEIS2C|id=A056193}} starts as follows:

{| class="wikitable" border="1"
|-
! Base !! Hereditary notation !! Value
|-
|    2 || <math> 2^{2^1} </math>                                                || 4
|-
|    3 || <math> 3^{3^1} - 1 = 2 \cdot 3^2 + 2 \cdot 3 + 2 </math>              || 26
|-
|    4 || <math> 2 \cdot 4^2 + 2 \cdot 4 + 1 </math>                        || 41
|-
|    5 || <math> 2 \cdot 5^2 + 2 \cdot 5 </math>                            || 60
|-
|    6 || <math> 2 \cdot 6^2 + 2 \cdot 6 - 1 = 2 \cdot 6^2 + 6 + 5 </math>  || 83
|-
|    7 || <math> 2 \cdot 7^2 + 7 + 4 </math>                                || 109
|- align=center
| <math> \vdots </math> || <math> \vdots </math> || <math> \vdots </math>
|-
|   11 || <math> 2 \cdot 11^2 + 11 </math>                                  || 253
|-
|   12 || <math> 2 \cdot 12^2 + 12 - 1 = 2 \cdot 12^2 + 11 </math>          || 299
|- align=center
| <math> \vdots </math> || <math> \vdots </math> || <math> \vdots </math>
|-
|   24 || <math> 2 \cdot 24^2 - 1 = 24^2 + 23 \cdot 24 + 23 </math>         || 1151
|- align=center
| <math> \vdots </math> || <math> \vdots </math> || <math> \vdots </math>
|-
| <math> B = 3 \cdot 2^{402\,653\,209} - 1 </math> || <math> 2 \cdot B^1 </math> || <math> 3 \cdot 2^{402\,653\,210} - 2 </math>
|-
| <math> B = 3 \cdot 2^{402\,653\,209} </math> || <math> 2 \cdot B^1 - 1 = B^1 + (B-1) </math> || <math> 3 \cdot 2^{402\,653\,210} - 1 </math>
|- align=center
| <math> \vdots </math> || <math> \vdots </math> || <math> \vdots </math>
|}

Elements of <math>G_4</math> continue to increase for a while, but at base <math>3 \cdot 2^{402\,653\,209}</math>,
they reach the maximum of <math>3 \cdot 2^{402\,653\,210} - 1</math>, stay there for the next <math>3 \cdot 2^{402\,653\,209}</math> steps, and then begin their descent.

However, even <math>G_4</math> doesn't give a good idea of just ''how'' quickly the elements of a Goodstein sequence can increase.
<math>G_{19}</math> increases much more rapidly and starts as follows:

{| class="wikitable" border="1"
|-
! Hereditary notation !! Value
|-
| <math> 2^{2^2} + 2 + 1 </math>   || 19
|-
| <math> 3^{3^3} + 3 </math>       || {{val|7,625,597,484,990}}
|-
| <math> 4^{4^4} + 3 </math>       || <math> \approx 1.3 \times 10^{154} </math>
|-
| <math> 5^{5^5} + 2 </math>       || <math> \approx 1.8 \times 10^{2\,184} </math>
|-
| <math> 6^{6^6} + 1 </math>       || <math> \approx 2.6 \times 10^{36\,305} </math>
|-
| <math> 7^{7^7} </math>           || <math> \approx 3.8 \times 10^{695\,974} </math>
|-
| 
<math> 8^{8^8} - 1 = 7 \cdot 8^{7 \cdot 8^7 + 7 \cdot 8^6 + 7 \cdot 8^5 + 7 \cdot 8^4 + 7 \cdot 8^3 + 7 \cdot 8^2 + 7 \cdot 8 + 7}</math> 
<math>{}+ 7 \cdot 8^{7 \cdot 8^7 + 7 \cdot 8^6 + 7 \cdot 8^5 + 7 \cdot 8^4 + 7 \cdot 8^3 + 7 \cdot 8^2 + 7 \cdot 8 + 6} + \cdots</math> 
<math>{}+ 7 \cdot 8^{8+2} + 7 \cdot 8^{8+1} + 7 \cdot 8^8 </math>
<math>{}+ 7 \cdot 8^7 + 7 \cdot 8^6 + 7 \cdot 8^5 + 7 \cdot 8^4 </math>
<math>{}+ 7 \cdot 8^3 + 7 \cdot 8^2 + 7 \cdot 8 + 7</math>
| <math> \approx 6.0 \times 10^{15\,151\,335} </math>
|-
| 
<math>7 \cdot 9^{7 \cdot 9^7 + 7 \cdot 9^6 + 7 \cdot 9^5 + 7 \cdot 9^4 + 7 \cdot 9^3 + 7 \cdot 9^2 + 7 \cdot 9 + 7}</math> 
<math>{}+ 7 \cdot 9^{7 \cdot 9^7 + 7 \cdot 9^6 + 7 \cdot 9^5 + 7 \cdot 9^4 + 7 \cdot 9^3 + 7 \cdot 9^2 + 7 \cdot 9 + 6} + \cdots</math> 
<math>{}+ 7 \cdot 9^{9+2} + 7 \cdot 9^{9+1}+ 7 \cdot 9^9 </math> 
<math>{}+ 7 \cdot 9^7 + 7 \cdot 9^6 + 7 \cdot 9^5 + 7 \cdot 9^4 </math>
<math>{}+ 7 \cdot 9^3 + 7 \cdot 9^2 + 7 \cdot 9 + 6</math>
| <math> \approx 5.6 \times 10^{35\,942\,384} </math>
|- align=center
| <math> \vdots </math>   || <math> \vdots </math>
|}

In spite of this rapid growth, Goodstein's theorem states that every Goodstein sequence eventually terminates at 0, no matter what the starting value is.