Généralisations de la suite de Fibonacci

Ce sont les suites de type Fibonacci d'ordre 3 ; avec pour premiers termes 0,0,1, on obtient la suite A000073 de l'OEIS :

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1 705, 3 136, 5 768, 10 609, 19 513, 35 890, 66 012…

La constante de Tribonacci : ${\displaystyle {\frac {1+{\sqrt[{3}]{19+3{\sqrt {33}}}}+{\sqrt[{3}]{19-3{\sqrt {33}}}}}{3}}={\frac {1+4\cosh \left({\tfrac {1}{3}}\cosh ^{-1}\left(2+{\tfrac {3}{8}}\right)\right)}{3}}\approx 1{,}839\,286\,755\,214\,161}$ dont les décimales sont données par la suite A058265 de l'OEIS , est la limite du quotient (suivant sur précédent) de deux termes consécutifs. C'est la solution positive de l'équation x³ − x² − x − 1 = 0 ainsi que la solution positive autre que 1 de x + x⁻³ = 2.

Cette constante intervient dans les coordonnées des sommets du cube adouci.

Son inverse, solution positive de x³ + x² + x = 1 a pour décimales la suite A192918 de l'OEIS.

Le terme d'indice n de la suite de Tribonacci commençant par 0, 0, 1 est : ${\displaystyle T_{n}=\left\lfloor 3b{\frac {\left({\frac {1}{3}}\left(a_{+}+a_{-}+1\right)\right)^{n}}{b^{2}-2b+4}}\right\rceil }$ où ${\displaystyle {\begin{aligned}a_{\pm }&={\sqrt[{3}]{19\pm 3{\sqrt {33}}}}\\b&={\sqrt[{3}]{586+102{\sqrt {33}}}}\end{aligned}}}$ et ${\displaystyle \left\lfloor .\right\rceil }$ désigne la fonction "entier le plus proche"[4].

Ce sont les suites de type Fibonacci d'ordre 4 ; avec pour premiers termes 0, 0, 0, 1, on obtient la suite A000078 de l'OEIS :

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, ...

La constante de Tétranacci, rapport limite de deux termes consécutifs, racine positive de l'équation x⁴ − x³ − x² − x − 1 = 0, ou x + x⁻⁴ = 2 , vaut environ 1,927561975482925 ( A086088) ; sa valeur exacte est[5] :

${\displaystyle \left(p_{1}+{\frac {1}{4}}\right)+{\sqrt {\left(p_{1}+{\frac {1}{4}}\right)^{2}-{\frac {2\lambda _{1}}{p_{1}}}\left(p_{1}+{\frac {1}{4}}\right)+{\frac {7}{24p_{1}}}+{\frac {1}{6}}}}}$

où

${\displaystyle p_{1}={\sqrt {\lambda _{1}+{\frac {11}{48}}}},\ \lambda _{1}={\frac {{\sqrt[{3}]{3{\sqrt {1689}}-65}}-{\sqrt[{3}]{3{\sqrt {1689}}+65}}}{12{\sqrt[{3}]{2}}}}}$.

Une suite où chaque terme est la somme des p précédents est désignée par suite de p-bonacci, ou p-nacci, avec des suffixes grecs pour les premières valeurs de p :

• Pentanacci : 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, ... suite A001591 de l'OEIS
• Hexanacci : 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, ... suite A001592 de l'OEIS
• Heptanacci : 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, ... suite A122189 de l'OEIS
• Octanacci : 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ... suite A079262 de l'OEIS
• Enneanacci : 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, ... suite A104144 de l'OEIS

La limite ${\displaystyle \alpha _{p}}$ du quotient de deux termes consécutifs de la suite de p-nacci est appelée constante de p-nacci ; c'est la solution positive de l'équation caractéristique : x^p = 1 + x + ... +x^{p – 1} ou celle de x + x^−p = 2 autre que 1

Elle permet d'obtenir une formule directe du terme d'indice n de la suite de p-nacci définie ci-dessus[5] :

${\displaystyle F_{n}^{(p)}=\left\lfloor {\frac {\alpha _{p}^{n-1}(\alpha _{p}-1)}{(p+1)\alpha _{p}-2p}}\right\rceil ,}$ où et ${\displaystyle \left\lfloor .\right\rceil }$ désigne la fonction "entier le plus proche".

On peut mettre des coefficients dans la relation de récurrence ; la suite de Padovan, et la suite de Perrin, vérifiant P_n+3 = P_n+1 + P_n, entrent dans cette catégorie, et, plus généralement, les suites suivantes.

Pour obtenir toutes les suites où chaque terme est une combinaison linéaire à coefficients entiers fixée des termes précédents, on définit la suite de Fibonacci générée par N (où N est un nombre rationnel positif) comme suit : si N = 2^a₁ × 3^a₂ × 5^a₃ × 7^a₄ × ... × p_r^a_r où p_r est le r-ième nombre premier, on pose :

${\displaystyle F_{N}(n)=a_{1}F_{N}(n-1)+a_{2}F_{N}(n-2)+a_{3}F_{N}(n-3)+a_{4}F_{N}(n-4)+a_{5}F_{N}(n-5)+...+a_{r}F_{N}(n-r)}$

avec les initialisations : F_N(n) = 0 pour n < r − 1, F_N`(r –1) = 1.

On obtient ainsi les cas précédents comme :

On peut supposer que chaque couple commence à engendrer à partir du p-ième mois suivant sa naissance (biologiquement ce serait p = 4 ou 5).

Posant u_n, le nombre de couples de lapins nés durant le mois n, et partant d'un couple au mois 1, le nombre demandé est F_n = u₁ + u₂ + ... + u_n ; comme u_n = F_n–p = F_n – F_n–1, la suite (F_n) est définie par :

${\displaystyle F_{n}=1{\text{ pour }}\ 1\leqslant n\leqslant p,{\text{ puis }}F_{n}=F_{n-1}+F_{n-p}}$.

• Pour p = 1 (la lapine met bas dès le mois suivant son mois de naissance), on trouve ${\displaystyle F_{n}=2^{n-1}}$.

• Pour p = 2, on obtient la suite de Fibonacci classique

• Pour p = 3, on obtient : 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277,... , suite A000930 de l'OEIS

Ici, un couple de lapins donne naissance à r nouveaux couples chaque mois et chaque couple commence à engendrer à partir du p-ième mois suivant sa naissance.

La suite donnant le nombre de lapins au mois n est alors définie par ${\displaystyle F_{n}=1{\text{ pour }}\ 1\leqslant n\leqslant p,{\text{ puis }}F_{n}=F_{n-1}+rF_{n-p}}$.

Pour p = 2 , on dispose de la formule exacte : ${\displaystyle F_{n}={\frac {{{\Bigl (}{\frac {1+{\sqrt {1+4r}}}{2}}}{\Bigr )}^{n}-{{\Bigl (}{\frac {1-{\sqrt {1+4r}}}{2}}}{\Bigr )}^{n}}{\sqrt {1+4r}}}}$, et la limite de ${\displaystyle F_{n+1}/F_{n}}$ est ${\displaystyle {\frac {1+{\sqrt {1+4r}}}{2}}}$. Exemples :

• pour r = 2, on obtient la suite de Jacobsthal : 1, 1, 3, 5, 11, 21, 43, 85, 171, 341,...,suite A001045 de l'OEIS , aussi dénommée suite de Bêta-nacci par Shari Lynn LEVINE [6].

On a dans ce cas tout simplement ${\displaystyle F_{n}={\frac {2^{n}-(-1)^{n}}{3}}}$ et ${\displaystyle F_{n+1}/F_{n}}$ tend vers 2.

• pour r = 3, on obtient la suite de Gamma-nacci : 1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, ..., suite A006130 de l'OEIS décalée d'un cran.
• pour r = 4, 5, 6, LEVINE a donné les noms de delta, êta , zêta - nacci.

Pour p = 3, r = 2, on obtient : 1, 1, 1, 3, 5, 7, 13, 23, 37, 63, 109,..., suite A077949 de l'OEIS décalée d'un cran.

Pour p = 3, r = 3, on obtient : 1, 1, 1, 4, 7, 10, 22, 43, 73, 139, 268,..., suite A084386 de l'OEIS décalée d'un cran.

On pose maintenant la condition que chaque lapin vit exactement q mois (i.e. meurt durant le q-ième mois suivant son mois de naissance), avec ${\displaystyle q>p\geqslant 1}$ , les portées étant toujours de r couples[7].

Plus précisément, une lapine qui naît le mois n, commence à procréer le mois n + p, continue de procréer jusqu'au mois n + q, et meurt à la fin de ce mois ; chaque couple donne donc naissance à r(q – p + 1) couples.

Si l'on pose :

• u_n, le nombre de couples de lapins nés durant le mois n
• F_n, le nombre de couples de lapins vivants à la fin du mois n.

La suite (u_n) peut être définie sur les entiers relatifs par :

• u_n = 0 pour n ≤ 0
• u₁ = 1
• u_n = r(u_{n –p} + u_{n –p – 1} + ... + u_{n –q}) pour n ≥ 2.

et on obtient F_n par la formule F_n = u_n + ... + u_{n –q + 1}.

La suite (F_n) peut être définie directement par récurrence d'ordre q :

F_n =r( F_{n –p} + F_{n –p – 1} + ... + F_{n –q}) pour n ≥ q + 1

les q premiers termes étant définis par :

• F_n = 1 pour 1 ≤ n ≤ p
• F_n = F_{n – 1} +r F_{n –p} pour p + 1 ≤ n ≤ q

Elle vérifie aussi la relation de récurrence plus simple, mais d'ordre q + 1 : F_n = F_{n –1} +r(F_{n –p} – F_{n –q – 1}) pour n ≥ q + 2.

1) Pour p = 2 et q = 3 (le couple met bas au bout de 2 mois, met bas puis meurt le mois suivant), on obtient la suite définie par :

${\displaystyle F_{1}=F_{2}=1,\ F_{3}=2,F_{n}=F_{n-2}+F_{n-3}}$

Soit 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151,...

vérifiant aussi la récurrence d'ordre 4 :

${\displaystyle F_{n}=F_{n-1}+F_{n-2}-F_{n-4}}$.

C'est la suite de Padovan décalée, suite A134816 de l'OEIS.

2) Pour p = 2 et q = 4, on obtient la suite définie par :

${\displaystyle F_{1}=F_{2}=1,F_{3}=2,F_{4}=3,F_{n}=F_{n-2}+F_{n-3}+F_{n-4}}$

Soit : 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277,...

Elle est aussi définie par récurrence d'ordre 3 :

${\displaystyle F_{1}=F_{2}=1,\ F_{3}=2,F_{n}=F_{n-1}+F_{n-3}}$

Et on a la récurrence d'ordre 5 :

${\displaystyle F_{n}=F_{n-1}+F_{n-2}-F_{n-5}}$

C'est la suite de Narayana, suite A000930 de l'OEIS.

• Cas le plus simple

Pour p = 1 , q = 2, r = 2, on obtient la suite définie par :

${\displaystyle F_{1}=1,F_{2}=3,\ F_{n}=2(F_{n-1}+F_{n-2})}$ : 1, 3, 8, 22, 60, 164, 448, 1224, 3344, 9136, 24960, 68192, ...., suite A028859 de l'OEIS décalée d'un cran.

• Suite de Vauban

Dans La cochonnerie, ou calcul estimatif pour connaître jusqu’où peut aller la production d’une truie pendant dix ans de temps (1699), Vauban montre qu’une seule truie a une descendance telle que, après douze générations, « il y a des porcs autant que l’Europe peut en nourrir ». Sa suite serait presque le cas p = 1 , q = 5, r = 6, avec une unité de temps égale à l'année au lieu du mois pour les lapins, sauf qu'il estime la première portée égale à 3 couples au lieu de 6.

La suite de Vauban est donc la suite (u_n) du nombre de naissances définie par :

• u_n = 0 pour n ≤ 0
• u₁ = 1
• u_n = 3u_{n – 1} + 6(u_{n –2} + u_{n – 3} + u_{n – 4} + u_{n –5}) pour n ≥ 2.

On obtient pour (u_n) : 1, 3, 15, 69, 321, 1491, 6921, 32139, 149229, 692919, ... suite A224749 de l'OEIS.

Une suite de Fibonacci aléatoire peut être définie lors d'un jeu de pile ou face, en prenant F_n = F_{n –1} + F_{n –2} si la pièce tombe sur pile, F_n = F_{n –1} –F_{n – 2} sinon. Une étude de Furstenberg et Kesten montre que cette suite croît presque sûrement de façon exponentielle avec un taux de variation constant : la constante est indépendante de la pièce jetée et a été calculée en 1999 par Divakar Viswanath. Elle est maintenant connue sous le nom de constante de Viswanath (suite A078416 de l'OEIS).

Un repfigit, ou nombre de Keith, est un entier naturel tel que, si l'on démarre une suite de type Fibonacci avec ses chiffres, le nombre d'origine finit par être atteint. Un exemple est 47, car la suite de type Fibonacci partant de 4 et 7 (4, 7, 11, 18, 29, 47) atteint 47. En base 10, les premiers repfigits sont :

14, 19, 28, 47, 61, 75, 197, 742, 1 104, 1 537, 2 208, 2 580, 3 684, 4 788, 7 385, 7 647, 7 909 (suite A007629 de l'OEIS).

La demi-suite de Fibonacci (suite A030067 de l'OEIS) est définie par la même récurrence que la suite de Fibonacci pour les termes d'indice impair : a_2n+1 = a_2n + a_{2n –1} mais pour les indices pairs par a_2n = a_n. La sous-suite des termes d'indice impair s_n = a_{2n –1} vérifie s_n+1 = s_n + a_n et est strictement croissante. Ses premiers termes :

1, 2, 3, 5, 6, 9, 11, 16, 17, 23, 26, 35, 37, 48, 53, 69, 70, 87, 93, 116, 119, 145, 154, ... (suite A030068 de l'OEIS)

Elle est définie par s_2n = s_n, et s_2n+1 = s_n + s_{n –1}, avec pour initialisation : s₀ = 0, s₁ = 1.