Généralisations de la suite de Fibonacci

En mathématiques, la suite de Fibonacci est définie par récurrence par :

F 0 = 0

F 1 = 1

F n = F n - 1 + F n - 2

, pour tout entier

n\geqslant 2

.

Autrement dit, les deux valeurs de départ 0 et 1 étant données, chaque nombre est la somme des deux précédents.

La suite de Fibonacci peut être généralisée de nombreuses façons ; par exemple, en partant d'autres nombres que 0 et 1, en ajoutant plus de deux termes pour générer le suivant, ou en ajoutant des objets autres que des nombres.

Extension aux entiers négatifs[modifier | modifier le code]

À l'aide de la relation $F n - 2 = F n - F n - 1$ , on peut étendre la suite de Fibonacci à des indices entiers négatifs. On obtient la suite : $..., -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...$ qui vérifie : $F - n = (-1) n +1 F n$ .

Extension aux nombres réels ou complexes[modifier | modifier le code]

Tracé de la courbe de la fonction Fib entre -5 et 5.

De manière similaire à la généralisation de la suite des factorielles par la fonction Gamma d'Euler, on peut construire une généralisation de la suite de Fibonacci à des valeurs de départ réelles (et même complexes).

Elle est basée sur la formule de Binet faisant intervenir le nombre d'or φ :

F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(\cos {n\pi })\varphi ^{-n}}{\sqrt {5}}}

.

En posant :

\mathrm {Fib} (z)={\frac {\varphi ^{z}-(\cos {\pi z})\varphi ^{-z}}{\sqrt {5}}}

on obtient une fonction holomorphe sur le plan complexe qui satisfait $Fib(n) = F n$ pour tout entier n^[1].

Elle vérifie aussi $Fib(z + 2) = Fib(z + 1) + Fib(z)$ pour tout complexe z.

Modification des termes initiaux[modifier | modifier le code]

On peut désigner par suite de type Fibonacci toute suite $(u n)$ à valeurs dans un espace vectoriel, vérifiant $u n +2 = u n +1 + u n$ pour tout naturel n. Ces suites peuvent aussi être définies par $u n = u 0 F n -1 + u 1 F n$ , de sorte qu'elles forment un plan vectoriel de base $((F n -1),(F n))$ . D'après la formule de Binet ci-dessus, une autre base de ce plan est $(φ n,(- φ) - n)$ .

Plus généralement, $(u n)$ peut prendre ses valeurs dans un groupe abélien (considéré comme un $\mathbb {Z}$ -module). Dans ce cas, les suites de type Fibonacci forment un $\mathbb {Z}$ -module de dimension 2.

La suite de type Fibonacci la plus connue après la suite $(F n)$ est la suite des nombres de Lucas $(L n)$ définie par $L 0 =2$ , $L 1 = 1$ et donc $L n +2 = L n +1 + L n$ ; prolongée aux entiers négatifs, elle vérifie aussi $L -n = (-1) n +1 L n$ .

Les suites d'entiers de type Fibonacci non triviales se trouvent toutes (éventuellement avec un décalage) sur une des lignes du tableau de Wythoff. La suite de Fibonacci en est la première ligne, et un décalage de celle de Lucas la deuxième^[2].

Modification des coefficients de la récurrence[modifier | modifier le code]

En reprenant les notations des suites de Lucas, on peut considérer les suites $(u n)$ vérifiant $u n +2 = p u n +1 - q u n$ où p et q sont des entiers fixés. Elles sont toutes combinaisons linéaires des deux suites de base $(U n), (V n)$ définies par :

U_{0}=0,U_{1}=1,U_{n+2}=pU_{n+1}-qU_{n}\quad {\text{  et  }}\quad V_{0}=2,V_{1}=1,V_{n+2}=pV_{n+1}-qV_{n}

(pour $p = 1, q = -1$ , $U n = F n$ et $V n = L n$ ).

Lorsque $q = -1$ , la suite $(U n)$ est appelée p-suite de Fibonacci et c'est aussi la valeur en p du polynôme de Fibonacci d'indice n. Exemples :

La 2-suite de Fibonacci est la suite de Pell.
La 3-suite de Fibonacci est la suite A006190 de l'OEIS :
0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, ...
La 4-suite de Fibonacci est la suite A001076 de l'OEIS :
0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, ...
La 5-suite de Fibonacci est, avec un décalage d'une unité, la suite A052918 de l'OEIS :
0, 1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275, 13741001, 71351280, 370497401, 1923838285, 9989688826, ...
La 6-suite de Fibonacci est la suite A005668 de l'OEIS :
0, 1, 6, 37, 228, 1405, 8658, 53353, 328776, 2026009, 12484830, 76934989, 474094764, 2921503573, 18003116202, ...

La p-constante de Fibonacci, appelée aussi p-ième nombre métallique, est la limite du rapport de deux nombres consécutifs de la p-suite de Fibonacci ; c'est l'unique solution positive de $x 2 - px - 1 = 0$ , égale à $p + \sqrt p 2 +4 / 2$ .

En particulier, pour $p = 1$ on obtient le nombre d'or $1 + \sqrt 5 / 2$ , pour $p = 2$ , le nombre d'argent 1 + √2, et sa valeur pour p = 3 , $3 + \sqrt 13 / 2$ , est parfois appelée nombre de bronze.

Plus généralement, $(U n)$ est appelée la $(p,- q)$ -suite de Fibonacci ; exemples :

La (1,2)-suite de Fibonacci est la suite de Jacobsthal, suite A001045 de l'OEIS :
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, ...
La (1,3)-suite de Fibonacci est la suite A006130 de l'OEIS :
0,1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689, 75316, 173383, 399331, 919480, 2117473, 4875913, 11228332, 25856071, 59541067, ...
La (2,2)-suite de Fibonacci est la suite A002605 de l'OEIS :
0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, 49920, 136384, 372608, 1017984, 2781184, 7598336, 20759040, 56714752, ...
La (3,3)-suite de Fibonacci est la suite A030195 de l'OEIS :
0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893, 507627, 1924560, 7296561, 27663363, 104879772, 397629405, 1507527531, 5715470808, ...

Articles détaillés : Suite de Lucas et Polynôme de Fibonacci.

Augmentation de l'ordre de la récurrence[modifier | modifier le code]

Une suite de type Fibonacci d'ordre p , ou suite de $p$ -bonacci, est une suite d'entiers dans laquelle chaque terme à partir du $p$ + 1-ième est la somme des $p$ précédents (le cas classique est $p$ = 2). Commençant à l'indice 0 et avec les $p$ premiers termes 0, 1, 1, 2, 4, ..., $2^{p-3}$ on la note $(F (p) n)$ .

Interprétations combinatoires :

Le nombre de listes d'entiers compris entre 1 et $p$ inclus dont la somme vaut $n$ (des compositions de $n$ ) est égal à $F (p) n +1$

Le nombre de jeux de pile ou face de longueur $n$ qui ne contiennent pas $p$ "pile" consécutifs (ou le nombre de parties de $[\![1,n]\!]$ ne contenant pas $p$ entiers consécutifs) est égal à et $F (p) n +2$ .

Ces suites ont été étudiées par Marc Barr en 1913^[3].

Les suites de Tribonacci[modifier | modifier le code]

Article détaillé : Suite de Tribonacci.

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 : ${\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$ , limite du quotient (suivant sur précédent) de deux termes consécutifs est étudiée dans l'article détaillé ci-dessus.

Les suites de Tétranacci[modifier | modifier le code]

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 4 - x 3 - x 2 - x - 1 = 0$ , ou $x + x -4 = 2$ , vaut environ 1,927561975482925 ( A086088) ; sa valeur exacte est^[4] :

\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ù

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}}}}

.

Suites d'ordres supérieurs[modifier | modifier le code]

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 $\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^[4] :

F_{n}^{(p)}=\left\lfloor {\frac {\alpha _{p}^{n-1}(\alpha _{p}-1)}{(p+1)\alpha _{p}-2p}}\right\rceil ,

où et

\left\lfloor .\right\rceil

désigne la fonction "entier le plus proche".

Article détaillé : Nombre_métallique#Deuxième_généralisation_:_constantes_de_p-nacci..

Autres généralisations[modifier | modifier le code]

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.

Suite générée par un rationnel[modifier | modifier le code]

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 1 \times 3 a 2 \times 5 a 3 \times 7 a 4 \times ... \times p r a r$ où $p r$ est le r-ième nombre premier, on pose :

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 :

Nom de la suite	N	Référence dans l'OEIS
suite de Fibonacci	6	suite A000045 de l'OEIS
suite de Pell	12	suite A000129 de l'OEIS
suite de Jacobsthal	18	suite A001045 de l'OEIS
suite de Tribonacci	30	suite A000073 de l'OEIS
suite de Tetranacci	210	suite A000078 de l'OEIS
suite de Padovan	15	suite A000931 de l'OEIS

Suites modélisant l'accroissement d'une population de lapins[modifier | modifier le code]

Partons du problème initial posé par Fibonacci : sachant qu'un couple de lapins donne naissance à un nouveau couple chaque mois et que chaque couple commence à engendrer à partir du deuxième mois suivant sa naissance, on demande le nombre total de couples au $n$ -ième mois.

Changement du délai de gestation[modifier | modifier le code]

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 1 + u 2 + ... + u n$ ; comme $u n = F n - p = F n - F n -1$ , la suite $(F n)$ est définie par :

$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 $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

Changement du nombre de couples dans la portée[modifier | modifier le code]

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 $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 : $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 $F_{n+1}/F_{n}$ est ${\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 ^[5].

On a dans ce cas tout simplement $F_{n}={\frac {2^{n}-(-1)^{n}}{3}}$ et $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.

Cas d'une durée de vie finie pour les lapins[modifier | modifier le code]

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 $q>p\geqslant 1$ , les portées étant toujours de r couples^[6].

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 \leq 0$
$u 1 = 1$
$u n = r (u n - p + u n - p - 1 + ... + u n - q)$ pour $n \geq 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 \geq q + 1

les $q$ premiers termes étant définis par :

$F n = 1$ pour $1 \leq n \leq p$
$F n = F n - 1 + r F n - p$ pour $p + 1 \leq n \leq 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 \geq q + 2$ .

Exemples pour r = 1 (1 couple par portée)[modifier | modifier le code]

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 :

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 :

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 :

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 :

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 :

F_{n}=F_{n-1}+F_{n-2}-F_{n-5}

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

Exemples avec r supérieur ou égal à 2[modifier | modifier le code]

Cas le plus simple

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

$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 \leq 0$
$u 1 = 1$
$u n = 3 u n - 1 + 6(u n -2 + u n - 3 + u n - 4 + u n -5)$ pour $n \geq 2$ .

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

Mot de Fibonacci[modifier | modifier le code]

Article détaillé : Mot de Fibonacci.

Par analogie avec la suite de Fibonacci numérique, la suite des mots de Fibonacci est définie par : $M_{0}=(b),M_{1}=(a),M_{n+2}=M_{n+1}\sqcup M_{n}$ où $\sqcup$ désigne la concaténation de deux mots. En ôtant les parenthèses, on obtient :

b, a, ab, aba, abaab, abaababa, abaababaabaab, ... (suite A106750 de l'OEIS)

La longueur de $M n$ est évidemment $F n$ et les mots de Fibonacci possèdent de nombreuses propriétés détaillées dans l'article correspondant.

Produits de convolution de la suite de Fibonacci[modifier | modifier le code]

Une suite de Fibonacci convolée est obtenue en effectuant, une ou plusieurs fois, le produit de convolution de la suite par elle-même. Plus précisément, on définit^[7] :

F_{n}^{(0)}=F_{n}\quad {\text{ et }}\quad F_{n}^{(r+1)}=\sum _{i=0}^{n}F_{i}F_{n-i}^{(r)}

.

Les premières suites sont

pour $r = 1$ : 0, 0, 1, 2, 5, 10, 20, 38, 71, ... (suite A001629 de l'OEIS).
pour $r = 2$ : 0, 0, 0, 1, 3, 9, 22, 51, 111, ... (suite A001628 de l'OEIS).
pour $r = 3$ : 0, 0, 0, 0, 1, 4, 14, 40, 105, ... (suite A001872 de l'OEIS).

Elles peuvent être calculées à l'aide de la relation de récurrence $F_{n+1}^{(r+1)}=F_{n}^{(r+1)}+F_{n-1}^{(r+1)}+F_{n}^{(r)}$ .

La fonction génératrice du r-ième produit de convolution est $s^{(r)}(x)=\sum _{k=0}^{\infty }F_{n}^{(r)}x^{n}=\left({\frac {x}{1-x-x^{2}}}\right)^{r}$ .

Ces suites sont liées à la suite $(P n)$ des polynômes de Fibonacci par la relation : $F (r) n = r! P (r) n (1)$ où $P (r) n$ est la r-ième dérivée de $P n$ . De manière équivalente, $F (r) n$ est le coefficient de $(x - 1) r$ lorsque $P n (x)$ est développé suivant les puissances de $x - 1$ .

Le premier produit de convolution peut être écrit en termes de nombres de Fibonacci et de Lucas :

F_{n}^{(1)}={\frac {nL_{n}-F_{n}}{5}}

et suit la récurrence

F_{n+1}^{(1)}=2F_{n}^{(1)}+F_{n-1}^{(1)}-2F_{n-2}^{(1)}-F_{n-3}^{(1)}

.

Des expressions similaires peuvent être trouvées pour $r > 1$ avec augmentation de la complexité à mesure que r augmente. Les nombres $F (r) n$ sont les sommes des lignes du triangle d' Hosoya (en).

Comme pour la suite de Fibonacci, il y a plusieurs interprétations combinatoires de ces suites. Par exemple, $F (1) n$ est le nombre de façons d'écrire $n - 2$ comme une somme de 0, de 1, et de 2 avec 0 utilisé exactement une fois. En particulier, $F (1) 4 = 5$ car 2 peut être écrit 0 + 1 + 1, 0 + 2, 1 + 0 + 1, 1 + 1 + 0, 2 + 0^[8].

D'autres généralisations[modifier | modifier le code]

Suite de Fibonacci aléatoire[modifier | modifier le code]

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).

Nombre de Keith[modifier | modifier le code]

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).

Demi-suite de Fibonacci[modifier | modifier le code]

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 2 n +1 = a 2 n + a 2 n -1$ mais pour les indices pairs par $a 2 n = a n$ . La sous-suite des termes d'indice impair $s n = a 2 n -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)

Suite diatonique de Stern[modifier | modifier le code]

Elle est définie par $s 2 n = s n$ , et $s 2 n +1 = s n + s n -1$ , avec pour initialisation : $s 0 = 0, s 1 = 1$ .

Article détaillé : Suite diatomique de Stern.

Voir aussi[modifier | modifier le code]

Les suites de Fibonacci modulo un entier.

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Generalizations of Fibonacci numbers » (voir la liste des auteurs).

↑ Pravin Chandra et Eric W. Weisstein. "Fibonacci Number". MathWorld.
↑ D. R. Morrison, A Collection of Manuscripts Related to the Fibonacci Sequence, Santa Clara, CA, The Fibonacci Association, 1980, 134–136 p. (lire en ligne).
↑ Martin Gardner, The Scientific American Book of Mathematical Puzzles and Diversions, Vol. II, Simon and Schuster, 1961, p. 101
↑ ^{a et b} D.A. Wolfram, « Solving Generalized Fibonacci Recurrences », Fib. Quart.,‎ 1998 (lire en ligne)
↑ (en) Shari Lynn LEVINE, « SUPPOSE MORE RABBITS ARE BORN »
↑ (en) V. E. Hoggatt, Jr. and D. A. Lind, « The dying rabbit problem », Fib. Quart. 7,‎ 1969, p. 482-487
↑ V. E. Hoggatt, Jr. and M. Bicknell-Johnson, "Fibonacci Convolution Sequences", Fib. Quart., 15 (1977), pp. 117-122.
↑ suite A001629 de l'OEIS

Liens externes[modifier | modifier le code]

(en) « Généralisations de la suite de Fibonacci », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)

[1] Pravin Chandra et Eric W. Weisstein. "Fibonacci Number". MathWorld.

[2] D. R. Morrison, A Collection of Manuscripts Related to the Fibonacci Sequence, Santa Clara, CA, The Fibonacci Association, 1980, 134–136 p. (lire en ligne).

[3] Martin Gardner, The Scientific American Book of Mathematical Puzzles and Diversions, Vol. II, Simon and Schuster, 1961, p. 101

[:0-4] {a et b} D.A. Wolfram, « Solving Generalized Fibonacci Recurrences », Fib. Quart.,‎ 1998 (lire en ligne)

[5] (en) Shari Lynn LEVINE, « SUPPOSE MORE RABBITS ARE BORN »

[6] (en) V. E. Hoggatt, Jr. and D. A. Lind, « The dying rabbit problem », Fib. Quart. 7,‎ 1969, p. 482-487

[7] V. E. Hoggatt, Jr. and M. Bicknell-Johnson, "Fibonacci Convolution Sequences", Fib. Quart., 15 (1977), pp. 117-122.

[8] suite A001629 de l'OEIS

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]