Ne pas croire ce qui croît
Une célèbre conjecture lycéenne dit que si une suite a l'air simple (1), à l'air de grimper vite au vu de sa définition (2) et a une croissance à peu près régulière sur ses premiers termes (3), alors cette suite est croissante ! Il est temps de vérifier la validité de cette étonnante conjecture !
Cette conjecture se vérifie bien avec des suites définies à base de fonctions puissances, du genre Un=2n. La suite a l'air simple, elle a l'air de grimper vite au vu de sa définition (ya une puissance, quand même) et a une croissance régulière, et même de plus en plus rapide, sur ses premiers termes (2, 4, 8, 16, 32, 64, 128...). Cette suite est bien croissante !
Prenons un autre exemple, alors : la suite de Goodstein (de graine 6), qui commence comme ça :
6, 29, 257, 3125, 46655, 98039, 187243, ...
Avec un petit graphique, ça donne :
Sur ses 30 premiers termes, cette suite a l'air de grimper de plus en plus vite, on vérifie bien la troisième partie de notre conjecture.
Mais comment est définie cette suite ?
* On part d'un nombre, (la graine, ici 6) qui sera le premier terme de la suite.
* On le décompose en base 2 itérée. C'est comme décomposer le nombre en base 2 (En somme de puissances de 2), sauf qu'on décompose également les puissances en base 2, jusqu'à n'avoir que des nombres inférieurs ou égaux à 3.*
Exemple avec 303 :
En base 2, 303 s'écrit 1×28+0×27+0×26+1×25+0×24+1×23+1×22+1×21+1×20
(Qui s'écrit plus agréablement 28+25+23+22+2+1)
Ensuite, on remplace 8, 5 et 3 par leur décomposition en base 2, ce qui donne : 
Il reste encore un 3, donc on le remplace par 2+1, ce qui donne la décomposition de 303 en base 2 itérée:
La décomposition de 6 en base 2 itérée est plus facile : 6=2²+2
* On remplace ensuite tous les 2 par des 3.
À partir de 303, on aurait 
(Ce qui vaut a peu près 4,43×1038)
À partir de 6, on aurait 3³+3 (=30)
* On soustrait ensuite 1, et on obtient le deuxième terme de la suite. Pour obtenir le suivant, on décomposera ce nombre en base 3 itérée, et on remplacera les 3 par des 4, et ainsi de suite.
Voici un petit script permettant de voir ces suites (Qui bugue dès que les valeurs deviennent trop grandes, ce n'est que du javascript) (Si je savais mettre du LaTeX directement dans mes pages, il y en aurait dans ce script, mais en attendant, il n'y a que la syntaxe...)
En tout cas, cette suite a une définition, certes tordue, mais assez simple. Elle ne met en jeu que la décomposition d'un nombre en une certaine base, et des remplacements. Elle vérifie bien le critère 1 de simplicité.
Et à le regarder de loin, on a des puissances de plus en plus grandes, ya pas de raisons, d'après sa définition, elle a l'air de plus en plus grande.
D'après notre géniale conjecture qui simplifie grandement le travail des mathématiciens, cette suite est toujours croissante !
Et évidement, si je parle de cette suite ici, c'est parce qu'elle contredit notre conjecture stupide :
Toutes les suites de Goodstein se terminent par 0 ! Saperlipopette !
Expliquons quand même ce mystère, je suis là pour ça.
La suite qui commence par 2 n'est pas la plus intéressante :
(Le Di->j désigne la transformation des i en j)
U0 = 2
U1 = D2->3(2)-1 = 3-1 = 2
U2 = D3->4(2)-1 = 2-1 = 1
U3 = D4->5(1)-1 = 1-1 = 0
La suite qui commence par 3 n'est pas la plus intéressante non plus :
U0 = 3
U1 = D2->3(2+1)-1 = (3+1)-1 = 3
U2 = D3->4(3)-1 = 4-1 = 3
U3 = D4->5(3)-1 = 3-1 = 2
U4 = D5->6(2)-1 = 2-1 = 1
U5 = D6->7(1)-1 = 1-1 = 0
Mais celle qui commence par 4 est déjà plus intéressante :
U0 = 4
U1 = D2->3(2²)-1 = (3³)-1 = 26
U2 = D3->4(2.3²+2.3+2)-1 = 2.4²+2.4+1
U3 = 2.5² + 2.5 + 0
U4 = 2.6² + 6 + 5
U5 = 2.7² + 7 + 4
U6 = 2.8² + 8 + 3
etc.
Ce que l'on peut remarquer, c'est qu'à partir du deuxième terme, la décomposition est toujours de la forme a.p²+b.p+c. Le nombre p est la base dans laquelle est décomposé le nombre (qui vaut n+2, n étant l'indice de la suite). En effet, la décomposition itérée en base p (>2) n'affectera pas les puissances, les seuls nombres qui seront modifiés par le remplacement seront les p)
Ainsi, quand on ne s'intéresse qu'aux coefficients a, b et c, on peut voir la suite comme ça :
* Quand le coefficient c est différent de 0, il n'y a que lui qui sera atteint par le -1.
* Si c=0 et b≠0, le coefficient b sera décrémenté, et c prendra la valeur p-1.
En effet, à la base p, on aura Un = a.p²+b.p et donc, Un+1 = a.(p+1)²+b.(p+1)-1. (Ce qui n'est pas une décomposition acceptable, il nous la faut en somme) On la transforme alors :
Un+1 = a.(p+1)²+b.(p+1)-1 = a.(p+1)²+(b-1).(p+1)+(p+1)-1 = a.(p+1)²+(b-1).(p+1)+p
* Si a≠0, b=0 et c=0, c'est a qui sera décrémenté ; b et c prendront les valeur courantes de la base.
En fait, les valeurs a b et c fonctionnent comme un compte à rebours. La différence, c'est qu'au lieu d'être en base 60 (1 h 00 min 00 sec -> 0h 59 min 59 sec...), c'est une base qui change en permanence, et qui est croissante.
Ainsi, les coefficients a b et c vont bien arriver à 0 à un moment ou un autre... Pour être précis, elle atteindra la valeur 0 lorsque p sera égal à 
(A peu près 120 millions de chiffres...)
Ca, c'est pour la suite qui commence par 4. Celle-ci a pour particularité de ne pas grandir si vite que ça... Si on commence par 18 ou 19, ça ira beaucoup plus vite au début ! Mais l'idée du compte à rebours reste à peu près valable.
Le théorème de Goodstein, qui dit que toute suite de Goodstein se termine par 0, est un théorème d'arithmétique. Il traite de nombre entier et n'utilise que des notions d'arithmétiques. Mais ce qui est fâcheux, c'est que c'est un théorème indémontrable... d'un point de vue arithmétique !
Kirby (La boule rose, pas le mathématicien)
Pour le démontrer, il faut passer utiliser des notions d'infinis (une sombre histoire d'ordinaux infinis) qui dépasse de loin le cadre de la théorie de l'arithmétique dans lequel le théorème est énoncé. Il est donc impossible de démontrer ce théorème par récurrence, même avec la meilleure imagination du monde, et ça, c'est Laurence Kirby (pas la boule rose, le mathématicien) et Jeffrey Paris qui le disent (Et ils l'ont rigoureusement démontré) !
Sources :
Pour la science n°278 Décembre 2000, L'infini est-il nécessaire ?