Suite diatomique de Stern

En mathématiques, la suite diatomique de Stern, ou suite de Stern-Brocot, est une suite d'entiers naturels introduite par le mathématicien Moritz Stern en 1858^[1], et dont les premiers termes sont :

Cette suite, notée ${\displaystyle ({\rm {fusc}}(n))}$est définie par récurrence de la façon suivante :

• ${\displaystyle {\rm {fusc}}(0)=0,{\rm {fusc}}(1)=1}$
• ${\displaystyle {\begin{cases}{\rm {fusc}}(2n)={\rm {fusc}}(n)\\{\rm {fusc}}(2n+1)={\rm {fusc}}(n)+{\rm {fusc}}(n+1)\end{cases}}}$

L'appellation "fusc" a été donnée, sans explication, par Edsger W. Dijkstra en 1976 ^[2],[3].

Un définition par récurrence double, proche de celle de la suite de Fibonacci, est, avec la même initialisation :

• ${\displaystyle {\rm {fusc}}(n+2)={\rm {fusc}}(n+1)+{\rm {fusc}}(n)-2({\rm {fusc}}(n){\text{ mod }}{\rm {fusc}}(n+1))}$^[4]

où ${\displaystyle a{\text{ mod }}b}$ est le reste de la division euclidienne de ${\displaystyle a}$ par ${\displaystyle b}$.

On peut construire la suite ligne par ligne en procédant selon la figure ci-contre. Omettant le premier terme 0, on part de la ligne 1 - 1. Puis chaque nouvelle ligne est recopiée de la ligne précédente en insérant des nombres, chaque nouveau nombre étant la somme des deux nombres situés de part et d'autre de sa position dans la ligne précédente.