Suite génératrice

Sans perte de généralité, on suppose que la suite a_n est en ordre non décroissant, et on définit la suite a_n comme la suite des sommes partielles de a_n comme :

${\displaystyle s_{n}=\sum _{m=0}^{n}a_{m}}$.

Alors, les conditions

${\displaystyle a_{0}=1\,}$

${\displaystyle 2a_{k}\geq a_{k+1}{\text{ pour tout }}k\geq 0}$

sont suffisantes pour qu'une suite a_n soit génératrice^[1],[2].

Un corollaire de ce qui précède établit que

${\displaystyle a_{0}=1\,}$

${\displaystyle s_{k-1}\geq a_{k}-1{\text{ pour tout }}k\geq 1}$

sont à la fois nécessaires et suffisantes pour qu'une suite a_n soit génératrice^[3].

Cependant, il existe des suites génératrices qui ne vérifient pas ce corollaire, par exemple la suite A203074 de l'OEIS, composées du nombre 1 et du plus petit nombre premier supérieur à chaque puissance de 2.

Les suites génératrices comprennent :

• La suite du nombre 1 suivi des nombres premiers (étudiée par SS Pillai et d'autres) ; ceci découle du postulat de Bertrand.
• La suite des nombres pratiques dont le premier terme est 1 et qui contient toutes les autres puissances de 2 comme sous-ensemble. suite A005153 de l'OEIS
• Les nombres de Fibonacci, ainsi que les nombres de Fibonacci auxquels on a retiré un nombre quelconque^[1]. Ceci découle de l'identité selon laquelle la somme des n premiers nombres de Fibonacci est le (n + 2)-ième nombre de Fibonacci moins 1.

De même que les puissances de deux forment une suite génératrice grâce au système binaire, toute suite génératrice peut en fait servir à encoder des entiers sous forme de chaînes de bits. Le bit le plus à droite correspond au premier élément de la séquence, le suivant au suivant, et ainsi de suite. Les bits à 1 sont inclus dans la somme. Ces représentations toutefois peuvent ne pas être uniques.

• Numérotation d'Ostrowski