Récurrence linéaire : du jeu à la formule, pas à pas

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Il faut s'imaginer un instant le scénario suivant. On est en 2012, en plein milieu du prestigieux championnat international de jeux mathématiques.

Intervenant 20:12

Ouais, l'ambiance devait être, disons, particulièrement tendue.

Intervenant 10:16

Ah mais totalement. Les participants sont penchés sur leurs feuilles, le silence est absolu, et surtout, point crucial, les calculatrices sont formellement interdites.

Intervenant 20:26

C'est la règle d'or de ce genre de compétition en fait. Tout se passe dans les têtes.

Intervenant 10:30

Exactement. Et là, au détour d'un problème qui a l'air super inoffensif, une équation exige soudainement de manipuler un nombre si gigantesque, mais vraiment absurdement colossal, qu'il ferait instantanément planter n'importe quel ordinateur qui essaierait de l'afficher en entier.

Intervenant 20:45

C'est fou quand on y pense. Et pourtant, ces compétiteurs devaient trouver le moyen de dompter ce monstre numérique à la seule force de leur cerveau.

Intervenant 10:55

C'est dingue ! Et c'est justement le point de départ de notre exploration d'aujourd'hui. On s'appuie sur le fascinant article « Récurrence linéaire et épidémie de bosses des maths ».

Intervenant 21:05

Un article super riche, oui. Qui revient sur ce fameux problème, le problème 1948, qui a d'ailleurs été republié plus tard dans le numéro 194 de Tangente en 2020.

Intervenant 11:15

Voilà. Donc notre mission aujourd'hui, eh bien décortiquons tout ça. On va soulever le capot de ce problème diabolique pour découvrir la mécanique, totalement invisible mais d'une élégance absolue, qui régit les suites récurrentes.

Intervenant 21:30

Je suis prête. Et tu sais, à première vue, ce genre d'énoncé, ça ressemble juste à une simple liste de nombres qui s'enchaînent. Un, puis deux, puis trois. Enfin, tu vois le genre.

Intervenant 11:41

Ouais, une bête file indienne de

Intervenant 21:42

chiffres. C'est ça. Mais derrière cette apparence très simple, il y a une architecture extrêmement profonde. Le véritable enjeu du championnat 2012, c'était pas du tout de faire du calcul brut.

Intervenant 11:53

Ben non, sans calculatrice, de toute façon, c'est mort.

Intervenant 21:55

Exactement. Le but, c'était de comprendre que les mathématiques offrent de véritables raccourcis spatio-temporels. Quand on affronte une suite récurrente, on a toujours l'impression d'être condamné à avancer pas à pas. De calculer le terme 1, puis le 2, puis le 3.

Intervenant 12:11

Ce qui prendrait un temps infini pour atteindre des rangs énormes.

Intervenant 22:13

Voilà, ce que l'énigme exigeait, c'était de trouver le passage secret pour sauter directement à la fin du temps, sans se taper toutes les étapes intermédiaires.

Intervenant 12:21

Mais ce concept de raccourci temporel, c'est fascinant. Par contre, pour comprendre comment on a pu contourner ce mur en 2012, je me dis qu'on ne peut pas attaquer la face nord de la montagne directement.

Intervenant 22:33

Ah bah non, on s'écraserait tout de suite.

Intervenant 12:34

C'est clair. Faut d'abord observer la mécanique de base, l'atome de cette logique, on va dire. La récurrence linéaire d'ordre 1. Bon, on sait tous plus ou moins que c'est une suite où un état dépend uniquement de son passé immédiat.

Intervenant 22:48

L'exemple le plus classique, c'est la suite géométrique.

Intervenant 12:50

Oui, c'est comme une recette de cuisine magique où chaque fournée est disons quatre fois plus grande que la précédente. On multiplie toujours par la même chose. Mais au-delà de cette simple multiplication, qu'est-ce que cet ordre 1 nous apprend fondamentalement sur la notion de prédiction ?

Intervenant 23:06

Ce qui nous apprend en fait, c'est la puissance de la traduction. Une récurrence linéaire d'ordre 1, où un terme u de n est égal à une constante k, multiplié par le terme précédent, c'est un processus dynamique, c'est un mouvement perpétuel.

Intervenant 13:18

D'accord.

Intervenant 23:19

La grande victoire mathématique ici, c'est de réussir à geler ce mouvement, d'en faire une formule pulement statique et directe. Au lieu de dire « pour avoir le terme de demain, je multiplie celui d'aujourd'hui par k ».

Intervenant 13:30

Ce qui nous oblige à connaître le terme d'aujourd'hui du coup ?

Intervenant 23:32

Exactement. Eh bien on traduit ça par n'importe quel jour n est égal au tout premier jour multiplié par k à la puissance n. La formule classique u de n égale u0 fois k puissance n.

Intervenant 13:44

Ah ouais, on transforme une boucle qui tourne sur elle-même en une fonction complètement explicite.

Intervenant 23:49

C'est ça, une métamorphose, on passe d'une loi de succession à une formule fermée. Et ça donne presque le vertige, parce que soudain on n'a plus du tout besoin du passé pour connaître l'avenir lointain.

Intervenant 14:00

C'est comme passer d'un mode d'emploi où tu dois suivre chaque étape à une vision omnisciente de tout le processus d'un seul coup. C'est brillant. Mais bon, la réalité est rarement aussi simple.

Intervenant 24:12

Non, malheureusement ou heureusement pour la bouteille des maths.

Intervenant 14:16

Ouais, voilà. La plupart des problèmes de championnat, ils ont une mémoire un peu plus longue. Si on passe à l'ordre 2, notre état présent ne dépend plus seulement d'hier, mais d'hier ET d'avant-hier. Absolument. Du coup, la formule, elle s'écrit avec deux paramètres, genre l'élément actuel, c'est une combinaison du précédent multiplié par A et de celui d'encore avant multiplié par B. Et c'est là que l'intuition spatiale rentre en jeu, parce que si je ne dis pas de bêtises, on bascule carrément dans un espace vectoriel de dimension 2, c'est bien ça.

Intervenant 24:45

C'est exactement ça et c'est le moment charnière de toute cette théorie. Un espace vectoriel de dimension 2, ça veut dire que l'infinité des solutions possibles pour cette règle, on peut la décrire avec seulement deux dimensions fondamentales.

Intervenant 14:57

Comme des coordonnées en fait.

Intervenant 24:58

Voilà. Un peu comme on a besoin d'une latitude et d'une longitude pour repérer n'importe quel point sur Terre. Et toute la difficulté, c'est de trouver ces deux axes de référence, ce qu'on appelle une base dans le jargon.

Intervenant 15:11

D'accord.

Intervenant 25:11

Et pour faire ça, les mathématiciens ont trouvé une ruse assez brillante. Ils construisent un pont conceptuel entre le monde des suites et le monde des polynômes.

Intervenant 15:20

Ah, c'est justement cette ruse que je voulais qu'on décortique. Parce que souvent quand on étudie ça, on nous parachute une équation du second degré sortie de nulle part en nous disant « bon bah voici l'équation caractéristique, trouvez les racines ».

Intervenant 25:33

C'est vrai que c'est souvent enseigné comme ça, un peu brutalement.

Intervenant 15:36

Oui, mais pourquoi diable un polynôme, avec des x² et tout, ça permet de résoudre une séquence qui avance dans le temps ? Quel est le lien caché ?

Intervenant 25:44

En fait, le mécanisme, il repose sur une hypothèse super audacieuse. Face à la complexité d'une suite d'ordre 2, on se pose une question très naïve. Est-ce qu'il existerait, par un heureux hasard, une suite d'ordre 1 toute bête, une pure progression géométrique du type r puissance n, qui fonctionnerait dans notre équation compliquée ?

Intervenant 16:05

Donc on tente de forcer une solution simple dans un problème complexe.

Intervenant 26:09

C'est exactement l'idée. On prend ce fameux r puissance n et on l'injecte de force dans la relation d'ordre 2. En faisant ça, on se retrouve avec r puissance n égal à a fois r puissance n moins 1 plus b fois r puissance n moins 2.

Intervenant 16:25

Ça a

Intervenant 26:27

l'air lourd, oui. Mais l'astuce, c'est de tout diviser par le plus petit terme, donc R puissance n-2. Et là, magie ! Toute la dimension temporelle s'évapore. Les fameux n disparaissent purement et simplement de l'équation.

Intervenant 16:41

Mais c'est génial, il ne reste plus qu'une structure pure en fait. Les puissances de N se contractent et on atterrit sur R² égale A fois R plus B. On vient littéralement de vaporiser le temps pour ne garder que le squelette, l'ADN de la croissance. C'est comme ça que naît l'équation caractéristique du second degré.

Intervenant 27:00

Exactement. C'est une vraie alchimie. Et en cherchant les racines de cette équation du second degré, disons deux racines distinctes qu'on appellerait P et Q, on trouve tout simplement nos deux axes fondamentaux.

Intervenant 17:12

Et la solution finale ?

Intervenant 27:14

Elle sera juste un savant mélange de P puissance n et de Q puissance n, qu'on ajuste ensuite selon les toutes premières valeurs de départ de la suite U et U .

Intervenant 17:24

Le principe est d'une élégance rare, franchement. Mais, parce qu'il y a un mais, je veux pousser la logique dans ses repranchements. On le sait bien, chercher les racines d'un polynôme du second degré, c'est risqué. Tu penses au fameux discriminant négatif, n'est-ce pas ?