Comme nous admirions les arbres de nos jardins aux ramifications innombrables, je félicitai mon élève, qui avait passé très brillamment son test en observant que la suite 1, 2, 4, 9 se poursuivait par 20, 48, 115, 286, ..., (1) et je profitai de son admirable pouvoir divinatoire pour lui poser quelques questions annexes :

Connais-tu lui dis-je, une suite remarquable débutant par 1 ?
- Bien sûr, c'est 1, 1, 1, ... me dit-il.

Et une suite qui débute par 1, 2 ?
- Naturellement, ce ne peut être que 1, 2, 4, 8, ... car la suite des nombres naturels 1, 2, 3, 4, ... est trop banale pour être remarquable.

Très bien ! Et puis, par 1, 2, 5, pour changer un peu ?

Presque immédiatement, il déclara que dans la suite des nombres de Fibonacci 1, 1, 2, 3, 5, 8, 13, ... où chaque terme est la somme des deux précédents, c'était lorsqu'on prenait les termes de deux en deux.

Parfait ! Et si je te donnais 1, 2, 5, 14 ?

- Alors, rétorqua-t-il, du triple de chacun j'enlèverais une unité pour trouver le suivant, soit 41 ensuite, puis 122, etc.

Et que ferais tu pour 1, 2, 5, 14, 42 ?
Allait-il me donner la suite des nombres de Catalan à laquelle je pensais dès le début, et dont le terme suivant est 132 ?
Sa réponse fut cependant 131.

Comment l'as-tu trouvé, lui dis-je ?

Il me fit alors une révélation lumineuse :

- J'avais en tête, m'expliqua-t-il, une suite bien remarquable A_n de polynômes. Partant de A₁ = 1-t qui assume la récurrence a_k = a_k-1 pour construire, à partir de a₀ = 1, la suite 1, 1, 1, ... et de A₂ = 1-2t qui, par a_k = 2a_k-1 fournit a₂ = 4 dans la suite 1, 2, 4, 8, ... et les termes qui suivent, je formai, selon la règle A_n+1 = A_n - tA_n-1 le polynôme A₃ = (1-2t) - t(1-t) = 1 - 3t + t² associé à la récurrence a_k = 3a_k-1 - a_k-2 qui, en partant de a₀ = 1 et a₁ = 2, donne a₂ = 5, comme il le fallait, puis a₃ = 13, etc. c'est-à-dire les nombres de Fibonacci pris de deux en deux, puisque de F_k+2 = F_k+1 + F_k, F_k+1 = F_k + F_k-1 et F_k = F_k-1 + F_k-2, l'on déduit par addition F_k+2 = F_k + 2F_k-1 + F_k-2, alors que F_k-1 = F_k - F_k-2, ce qui donne enfin F_k+2 = 3F_k - F_k-2 pour la récurrence en parité.

C'est incontestable, approuvai-je. Mais ensuite ?
- Ensuite, formant A₄ = (1-3t+t²) - t(1-2t) = 1-4t+3t², je considérai la récurrence a_k = 4a_k-1 - 3a_k-2 qui, avec les conditions initiales a₀ = 1, a₁ = 2, fournit d'abord a₂ = 5 et a₃ = 14 comme demandé, puis a₄ = 41, et généralement a_k = ½ (3^k+1) comme a_k = 3a_k-1-1

Remarquable ! La vérification en effet est immédiate, et si l'on peut préférer la simplicité de cette dernière récurrence, elle n'est pas pour autant de la forme générale de celles qui précèdent, à cause du terme constant -1.

Et qu'en est-il après ?

- Eh bien ! Avec A₅ = 1-5t+6t²-t³, du départ a₀ = 1, a₁ = 2, a₂ = 5 l'on arrive, après a₃ = 14 et a₄ = 42, que vous imposiez, à a₅ = 131. Vous voyez ainsi, sans ambiguïté, comment ce nombre m'est apparu.

Je ne pouvais pas en disconvenir, mais comme j'étais décidé à lui faire entrevoir la suite des nombres de Catalan qui figure combien il est possible de faire des décompositions en triangles d'un polygone convexe plan par des diagonales qui ne se coupent pas, je plaçai la barre encore plus haut, en lui proposant 1, 2, 5, 14, 42, 132 en tant que conditions initiales, espérant qu'il trouverait à ce point le nombre suivant 429.

Ce fut pourtant 428 qui sortit de son calcul pour le nombre a₆, et je compris alors qu'il était inutile d'aller plus loin, car chaque épreuve lui donnait par son procédé, pour le nombre succédant au dernier de ceux que je lui suggérais, une unité de moins que celui que je voulais.

Il me fallut donc lui expliquer ce qu'étaient ces nombres de Catalan, en dessous desquels il plaçait toujours les siens, d'une façon valable et générale, mais différente de celle que j'attendais. Si loin que j'aurais pu aller dans l'énumération des termes de la suite que j'envisageais, il était toujours en mesure d'en construire une autre, dont les termes cessaient, après ceux que j'avais donnés, de coïncider avec les suivants. Il comprit que les nombres que je lui révélai constituaient pour toutes les suites de son invention un plafond inaccessible, parce qu'ils possédaient une croissance plus rapide, et que bien qu'il puisse les rattraper à la course sur un parcours fini, de quelque longueur qu'il le veuille, il n'y parviendrait jamais définitivement.

Il eut de cela une grande satisfaction, et quand je lui indiquai sous la forme explicite l'expression de ces nombres en terme des binomiaux, il me demanda si quelque relation de récurrence pouvait les engendrer.

Il faudrait, lui dis-je, que nous parlions de cela plus en détail, car il est de telles relations qui ne sont pas linéaires (2), et de celles-là justement dépendent les nombres de Catalan. Ton procédé (3) en constituait une sorte d'approximation, comme font les sommes partielles dans une série infinie. Tu les retrouveras dans la diagonale du tableau suivant :

 

1	1	1	1	1	1	1	...
1	2	4	8	16	32	64	...
1	2	5	13	34	89	233	...
1	2	5	14	41	122	365	...
1	2	5	14	42	131	417	...
1	2	5	14	42	132	428	...
1	2	5	14	42	132	429	...