Suite de Fibonacci

La suite de Fibonacci est une suite d'entiers particulièrement connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, décrit...

Catégories :

Suite d'entiers

Page(s) en rapport avec ce sujet :

Suite de nombres introduite p a r le mathématicien italien Fibonacci..... Le ratio entre deux nombres successifs de la suite de Fibonacci tend vers le ... (source : villemin.gerard.free)
SUITE DE FIBONACCI - NOMBRE D'OR. TS. Dans ce devoir, on s'interesse aux suites (un) qui vérifient la relation de récurrence : un+2 = un+1 + un... (source : pagesperso-orange)

La suite de Fibonacci est une suite d'entiers particulièrement connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, décrit la croissance d'une population de lapins :

«Un homme met un couple de lapins dans un lieu isolé de l'ensemble des côtés par un mur. Combien de couples obtient-on en un an si chaque couple génère l'ensemble des mois un nouveau couple à compter du troisième mois de son existence ?»

Ce problème est à l'origine de la suite dont le $n\,$ -ème terme correspond au nombre de paires de lapins au $n\,$ -ème mois. Dans cette population (idéale), on suppose que :

au (début du ) premier mois, il y a juste une paire de lapereaux ;
les lapereaux ne procréent qu'à partir du (début du ) troisième mois ;
chaque (début de ) mois, toute paire susceptible de procréer génère effectivement une nouvelle paire de lapereaux ;
les lapins ne meurent jamais (donc la suite de Fibonacci est strictement croissante).

Présentation mathématique

Formule de récurrence

Notons $\mathcal{F}_n$ le nombre de couples de lapins au début du mois $n\,$ . Jusqu'à la fin du deuxième mois, la population se limite à un couple (ce qu'on note : $\mathcal{F}_1=\mathcal{F}_2=1$ ). Dès le début du troisième mois, le couple de lapins a deux mois et il génère un autre couple de lapins. On note alors $\mathcal{F}_3=2$ . Plaçons-nous désormais au mois $n\,$ et cherchons à exprimer ce qu'il en sera deux mois plus tard $(n + 2)\,$ : $\mathcal{F}_{n+2}$ sert à désigner la somme des couples de lapins au mois $n + 1\,$ et des couples nouvellement génèrés. Or, n'engendrent au mois $(n + 2)\,$ que les couples pubères, c'est-à-dire ceux qui existent deux mois jusque là. On a donc :

$\mathcal{F}_{n+2}=\mathcal{F}_{n+1}+\mathcal{F}_n$ .

Nous obtenons ainsi la forme récurrente de la suite de Fibonacci : chaque terme de cette suite est la somme des deux termes qui ont précédé ; pour obtenir chacun de ces deux termes, il faut faire la somme de leurs termes qui ont précédé… et ainsi de suite, jusqu'à ce que ces deux termes soient les deux termes initiaux, $\mathcal{F}_1$ et $\mathcal{F}_2$ , qui sont connus.

Nombres de Fibonacci

Les termes de cette suite sont nommés nombres de Fibonacci (suite A000045 de l'ŒIS) :

$\mathcal{F}_0$	$\mathcal{F}_1$	$\mathcal{F}_2$	$\mathcal{F}_3$	$\mathcal{F}_4$	$\mathcal{F}_5$	$\mathcal{F}_6$	$\mathcal{F}_7$	$\mathcal{F}_8$	$\mathcal{F}_9$	$\mathcal{F}_{10}$	$\mathcal{F}_{11}$	$\mathcal{F}_{12}$	$\mathcal{F}_{13}$	$\mathcal{F}_{14}$	$\mathcal{F}_{15}$	$\mathcal{F}_{16}$	$\mathcal{F}_{17}$	$\mathcal{F}_{18}$	$\mathcal{F}_{19}$	$\mathcal{F}_{20}$	$\mathcal{F}_{21}$	$\mathcal{F}_{22}$	$\mathcal{F}_{23}$	$\mathcal{F}_{24}$	$\mathcal{F}_{25}$	...	$\mathcal{F}_{n}$
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765	10946	17711	28657	46368	75025	...	$\mathcal F_{n-1}+\mathcal F_{n-2}$

Expression fonctionnelle

On souhaite établir une expression fonctionnelle de la suite de Fibonacci, c'est-à-dire une expression telle que le calcul du nombre de couples pour une valeur de $n\,$ donnée ne présuppose la connaissance d'aucun nombre de couples pour une quelconque autre valeur de $n\,$ , ce que ne permet pas la formule de récurrence. Comme la suite de Fibonacci est récurrente d'ordre deux, on peut écrire son équation caractéristique. On obtient une équation du second degré : $xˆ2 = x + 1\,$

$xˆ2 - x - 1 =0\,$ .

Le calcul du discriminant de cette équation donne les deux solutions du polynôme :

$x_1 = \varphi = \frac{1+\sqrt{5}}{2}\,$ et $x_2 = \varphi' = \frac{1-\sqrt{5}}{2}= -\frac{1}{\varphi}\,$ . ( $\varphi\,$ est le nombre d'or).

Les suites $(\varphiˆn)$ et $(\varphi'ˆn)$ génèrent alors l'espace vectoriel des suites vérifiant $u n + 2 = u n + 1 + u n$ . Il en résulte que :

$\mathcal{F}_n = \alpha{}\varphiˆn+\beta\varphi'ˆn$ ( $\alpha\,$ et $\beta\,$ sont des constantes à déterminer à partir de $\mathcal{F}_0$ et $\mathcal{F}_1$ . )

Les conditions initiales $\mathcal{F}_0=0$ et $\mathcal{F}_1=1$ amènent au dispositif suivant :

$\left\{\begin{matrix} \alpha + \beta = 0 \\ \alpha - \beta = \frac{2}{\sqrt{5}}\end{matrix}\right.$

Ce qui donne le résultat suivant :

$\alpha = \frac{1}{\sqrt{5}}$ et $\beta = -\frac{1}{\sqrt{5}}$ .

Nous obtenons finalement l'expression fonctionnelle recherchée, qui porte le nom de formule de Binet :

$\mathcal{F}_n = \frac{1}{\sqrt{5}}(\varphiˆn-\varphi'ˆn)$ .

Il existe d'autres démonstrations telles que la transformation en Z et la technique des fonctions génératrices.

Remarquons qu'une fois découverte cette formule se démontre aussi par récurrence.

La suite pour les nombres négatifs

En général, on n'étudie pas les nombres de Fibonacci pour des valeurs négatives de n, quoiqu'ils existent et soient aisément déterminables avec la formule récurrente. Il existe ainsi une règle particulièrement simple pour calculer ces nombres lorsque $n < 0$ :

si n est pair alors $\mathcal{F}_{-n} = -\mathcal{F}_n$
si n est impair alors $\mathcal{F}_{-n} = \mathcal{F}_n$

Ainsi, autour de 0, la séquence est :

$\ldots,\;-8,\;5,\;-3,\;2,\;-1,\;1,\;0,\;1,\;1,\;2,\;3,\;5,\;8,\;\ldots$

Limite des quotients

Comme l'a remarqué Johannes Kepler, le taux de croissance des nombres de Fibonacci, c'est-à-dire $\frac{\mathcal{F}_{n+1}}{\mathcal{F}_n}$ , converge vers le nombre d'or, noté $\varphi\,$ . Mathématiquement, le résultat s'obtient ainsi :

$\lim_{n \to \infty}\frac{\mathcal{F}_{n+1}}{\mathcal{F}_n}$	$=\lim_{n \to \infty}\frac{\varphiˆ{n+1}-\varphi'ˆ{n+1}}{\varphiˆn-\varphi'ˆn}$
	$=\lim_{n \to \infty}\varphi\frac{1-(\varphi'/\varphi)ˆ{n+1}}{1-(\varphi'/\varphi)ˆn}$	(en simplifiant par $\varphiˆn\,$ )
	$=\varphi\,$	(comme $\varphi'/\varphi \in ]-1;1[$ , $\lim_{n \to \infty}(\varphi'/\varphi)ˆn = 0$ )

Plus exactement, lorsque $n\,$ tend vers l'infini, le second terme tend vers zéro car $\varphi' \in ]-1 ; 1[$ , ainsi les nombres de Fibonacci se comportent comme une exponentielle multipliée par le facteur $\frac{1}{\sqrt{5}}$ , soit $\frac{\varphiˆn}{\sqrt{5}}$ .

En réalité, dès le rang $n=1\,$ , le deuxième terme ${\varphi'ˆn \over \sqrt{5}}$ est assez petit pour que les nombres de Fibonacci puissent être obtenus seulement à partir du premier terme, en arrondissant à l'entier le plus proche.

Bases et espaces vectoriels

L'expression de «suite de Fibonacci généralisée» est attribuée d'une façon plus générale à toute fonction $\mathcal{G}$ définie sur $\mathbb N$ vérifiant pour tout entier naturel $n\,$ , $\mathcal{G}_{n+2}=\mathcal{G}_{n+1}+\mathcal{G}_n$ . Ces fonctions sont exactement celles pour lesquelles il existe des nombres a et b, tels que pour tout entier naturel n, $\mathcal{G}_n = a{}\cdot{}\mathcal{F}_n+b{}\cdot{}\mathcal{F}_{n+1}$ . Ainsi, la totalité des suites de Fibonacci est un espace vectoriel, et les suites $(\mathcal{F}_n)$ et $(\mathcal{F}_{n+1})$ en forment une base.

Le nombre d'or est la racine positive de l'équation du second degré $xˆ2 - x - 1 = 0\,$ , ainsi $\varphiˆ2 = \varphi + 1\,$ . Si on multiplie les deux côtés par $\varphiˆn\,$ , on obtient $\varphiˆ{n+2} = \varphiˆ{n+1} + \varphiˆn\,$ , par conséquent la fonction $n\mapsto \varphiˆn$ est une suite de Fibonacci. La racine négative de l'équation du second degré, $\varphi'=1-\varphi\,$ , possède les mêmes propriétés, et les deux fonctions linéairement indépendantes $n\mapsto \varphiˆn$ et $n\mapsto \left(1-\varphi\right)ˆn$ , forment une autre base de l'espace vectoriel.

Algorithmes de calcul des nombres de Fibonacci

Avec la formule de Binet

Calculer les nombres de Fibonacci à partir du nombre d'or est une possibilité particulièrement pratique. Néanmoins, la précision de calcul de la racine carrée génère des erreurs d'arrondis pour des valeurs assez grandes dépendant du dispositif utilisé. Généralement, on obtient les bonnes valeurs jusqu'à $\mathcal{F}_{71} = 308061521170130$ , sur ordinateur ou sur calculatrice.

Notons qu'au-delà de $\mathcal{F}_{79}$ , les calculs dépassent les possibilités de calcul en notation entière, et sont alors représentés en notation scientifique. Les premiers chiffres significatifs sont alors de nouveau bien représentés par cette formule.

Détail d'un exemple d'application faisable à partir d'une calculatrice : Calcul de $\mathcal{F}_{50}$ .

Le nombre d'or vaut : $\frac{1+\sqrt{5}}{2}\ = 1,61803398874989\dots$

Appliquons la formule de Binet, (en ne retenant que le terme significatif) soit :

$\mathcal{F}_{50} \approx \frac{(1,61803398874989)ˆ{50}}{\sqrt{5}} \approx 12586269024,9981$

Arrondissons à l'entier le plus proche soit :

$\mathcal{F}_{50} = 12586269025$

Algorithme récursif naïf

L'implémentation récursive naïve qui suit la définition de la suite de Fibonacci est immédiate. En Python, cela donne :

def fibo(n):
    if (n <= 1):  # cas de base
        return n    # si n=0 return 0, si n=1 return 1 
    else:         # récurrence
        return fibo(n - 1) + fibo(n - 2)

Ce n'est cependant pas une façon judicieuse de calculer la suite de Fibonacci, car on calcule de nombreuses fois les mêmes valeurs (à moins d'employer une technique de mémoization). Le temps de calcul s'avère exponentiel.

Algorithme linéaire

Un moyen énormément plus efficace de calculer la suite de Fibonacci consiste à calculer simultanément deux valeurs consécutives de la suite, c'est-à-dire en commençant avec les deux premières valeurs 0 et 1, et en remplaçant répétitivement le premier nombre par le second, et le second nombre par la somme des deux.

En Python, un tel algorithme itératif donne :

def fibo(n):
    f_n_1 = 1  # F_{-1} = 1
    f_n = 0    # F_0 = 0
    for i in range(n):  # n fois
        f_n_1, f_n = (f_n, f_n + f_n_1)
    return f_n

De manière équivalente, on peut écrire une fonction récursive terminale :

def fibo(n, f_n_1 = 1, f_n = 0):  # (n, F_{n-1}, F_n)
    if (n == 0):  # cas de base
        return f_n
    else:         # récurrence
        return fibo(n - 1, f_n, f_n + f_n_1)

Le temps de calcul est à chaque fois proportionnel à n et l'espace mémoire occupé constant.

Algorithme logarithmique

En utilisant la relation matricielle suivante, qu'on montre par récurrence :

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}ˆn = \begin{bmatrix} \mathcal F_{n+1} & \mathcal F_n \\ \mathcal F_n & \mathcal F_{n-1} \end{bmatrix}$

ou avec les #Propriétés de la suite de Fibonacci, on obtient :

$\mathcal F_{2k} = 2\mathcal F_{k-1} \mathcal F_k + \mathcal F_kˆ2 = (2 \mathcal F_{k-1} + \mathcal F_k) \mathcal F_k$

$\mathcal F_{2k+1} = \mathcal F_{k+1}ˆ2 + \mathcal F_kˆ2$

En prenant bien soin de ne pas calculer deux fois les mêmes éléments, on obtient alors un algorithme dont le temps de calcul est proportionnel au logarithme de n. Voici un exemple de programme en Python :

def fibo2(n):
    """Renvoie F_{n-1}, F_n"""
    if (n == 0):  # cas de base
        return 1, 0  # F_{-1}, F_0
    else:         # récurrence
        f_k_1, f_k = fibo2(n//2)        # F_{k-1}, F_k   avec k = n/2
        f2_k = f_k**2                   # F_k^2
        if n%2 == 0:  # n pair
            return f2_k + f_k_1**2,    f_k*f_k_1*2 + f2_k       # F_{2k-1}, F_{2k}
        else:         # n impair
            return f_k*f_k_1*2 + f2_k, (f_k + f_k_1)**2 + f2_k  # F_{2k},   F_{2k+1}
 
def fibo(n):
    """Renvoie F_n"""
    return fibo2(n)[1]

En reœuvrant les relations de récurrence pour le cas pair on obtient :

$\mathcal F_{2k} = \mathcal F_{2k+1} - \mathcal F_{2k-1} = (\mathcal F_{k+1}ˆ2 + \mathcal F_kˆ2) - (\mathcal F_kˆ2 + \mathcal F_{k-1}ˆ2) = \mathcal F_{k+1}ˆ2 - \mathcal F_{k-1}ˆ2$

Et donc :

$\forall n \in \mathbb{Z}, \mathcal F_{n} = \mathcal F_{\lfloor\frac{n}{2}\rfloor+1}ˆ2 - (-1)ˆn \mathcal F_{\lfloor\frac{n-1}{2}\rfloor}ˆ2$

Curiosité algorithmique

Une façon spécifiquement curieuse d'obtenir la suite de Fibonacci est la suivante. On considère la liste de fractions [23/95, 57/23, 17/39, 130/17, 11/14, 35/11, 19/13, 1/19, 35/2, 13/7, 7]. Si on part d'un entier de la forme $2 F (n - 1) 3 F (n)$ et si on le multiplie itérativement par la première fraction qui redonne un résultat entier, alors le premier nombre entier de la suite ainsi obtenue qui n'aura que 2 et 3 comme facteurs premiers sera le nombre $2 F (n) 3 F (n + 1)$ .

A titre d'exemple, si on part de $18 = 2 132$ , on obtient successivement :

18 $\times$ 35/2 = 315

315 $\times$ 13/7 = 585

585 $\times$ 17/39 = 255

255 $\times$ 130/17 = 1950

1950 $\times$ 17/39 = 850

850 $\times$ 130/17 = 6500

6500 $\times$ 19/13 = 9500

9500 $\times$ 23/95 = 2300

2300 $\times$ 57/23 = 5700

5700 $\times$ 23/95 = 1380

1380 $\times$ 57/23 = 3420

3420 $\times$ 23/95 = 828

828 $\times$ 57/23 = 2052

2052 $\times$ 1/19 = 108 =

2233

Si on itère le procédé, on verra défiler les nombres de Fibonacci dans les exposants des puissances de 2 et 3 décomposant les nombres ainsi obtenus.

Propriétés de la suite de Fibonacci

La suite de Fibonacci, ainsi définie, présente de remarquables propriétés. En voici quelques-unes, données avec leur démonstration (celles-ci font généralement appel au raisonnement par récurrence). Nous donnons aussi quelques propriétés liant la suite de Fibonacci et les nombres de Lucas.

Propriété 1 : $\forall (p,q)\in\mathbb{N}ˆ*\times\mathbb{N}, \mathcal{F}_{p+q} = \mathcal{F}_{p-1}\mathcal{F}_q + \mathcal{F}_p\mathcal{F}_{q+1}$

Démonstration

Par récurrence d'ordre 2 sur $q\,$

Initialisation

(rang $q=0\,$ ) : $\mathcal{F}_{p-1}\mathcal{F}_0 + \mathcal{F}_p\mathcal{F}_1 = \mathcal{F}_p$

(rang $q=1\,$ ) : $\mathcal{F}_{p-1}\mathcal{F}_1 + \mathcal{F}_p\mathcal{F}_2 = \mathcal{F}_{p+1}$ (Définition de la suite de Fibonacci)

Hypothèses de récurrence :

(au rang $q\,$ ), $\mathcal{F}_{p+q} = \mathcal{F}_{p-1}\mathcal{F}_q + \mathcal{F}_p\mathcal{F}_{q+1}$

(au rang $q+1\,$ ), $\mathcal{F}_{p+q+1} = \mathcal{F}_{p-1}\mathcal{F}_{q+1} + \mathcal{F}_p\mathcal{F}_{q+2}$

Hérédité (rang $q+2\,$ ) :

$\mathcal{F}_{p+(q+2)}=\mathcal{F}_{p+q+1} + \mathcal{F}_{p+q}$ (Définition de la suite de Fibonacci)

$\mathcal{F}_{p+(q+2)}=\mathcal{F}_{p-1}\mathcal{F}_{q+1} + \mathcal{F}_p\mathcal{F}_{q+2} + \mathcal{F}_{p-1}\mathcal{F}_{q} + \mathcal{F}_p\mathcal{F}_{q+1}$ (Hypothèses de récurrence)

$\mathcal{F}_{p+(q+2)}=\mathcal{F}_{p-1}(\mathcal{F}_{q}+\mathcal{F}_{q+1})+\mathcal{F}_p(\mathcal{F}_{q+1}+\mathcal{F}_{q+2})$ (Factorisation)

$\mathcal{F}_{p+(q+2)}=\mathcal{F}_{p-1}\mathcal{F}_{q+2} + \mathcal{F}_p\mathcal{F}_{(q+2)+1}$ (Définition)

Propriété 2 : $\forall (k,n)\in\mathbb{N}\times\mathbb{N}ˆ*, \mathcal{F}_n{}|{}\mathcal{F}_{n\cdot k}$

Démonstration

Par récurrence sur $k\,$

Initialisation (rang $k=0\,$ ) : $\mathcal{F}_n{}|{}0$ (vrai car tout entier naturel divise 0)
Hypothèse de récurrence : au rang $k\,$ , $\mathcal{F}_n{}|{}\mathcal{F}_{n\cdot k}$
Hérédité (rang $k+1\,$ ) :

$\mathcal{F}_{n\cdot(k+1)}=\mathcal{F}_{n-1}\mathcal{F}_{n\cdot k}+\mathcal{F}_{n}\mathcal{F}_{n\cdot k + 1}$ (Propriété 1)

$\mathcal{F}_{n\cdot(k+1)}=\mathcal{F}_n(\lambda\cdot\mathcal{F}_{n-1}+\mathcal{F}_{n\cdot k+1})$ (Hypothèse de récurrence)

$\mathcal{F}_{n\cdot(k+1)}=\mu\cdot\mathcal{F}_n$

Corollaire : si $n\,\neq\,4$ et $\mathcal{F}_n$ est premier, $n\,$ est premier.

En effet, supposons $n\,$ composé. Si $m\,$ est un diviseur propre de $n\,$ , on a selon la propriété 2 : $\mathcal{F}_m{}|{}\mathcal{F}_{n}$ , au contraire de l'hypothèse que $\mathcal{F}_n$ est premier. Par conséquent $n\,$ est premier.

On peut écrire le corollaire comme suit, en désignant par $\mathbb{P}$ la totalité des nombres premiers :

$\forall n \in \mathbb{N}\setminus\{4\}, \mathcal{F}_n\in\mathbb{P}{}\Rightarrow{}n\in\mathbb{P}$

La réciproque est fausse, car $2\in\mathbb{P},\mathcal{F}_2{}\not\in{}\mathbb{P}$ .

Propriété 3 : $\forall (k,n)\in\mathbb{N}ˆ2{}/{}n{}\ge{}k{}\ge{}0, \mathcal{F}_n{}\mathcal{F}_{k+1}-\mathcal{F}_k\mathcal{F}_{n+1}=(-1)ˆk\mathcal{F}_{n-k}$

Démonstration

Par récurrence sur k

Initialisation (rang k = 0) : $\forall n \geq 0,\quad \mathcal{F}_n\mathcal{F}_1-\mathcal{F}_0\mathcal{F}_{n+1}=\mathcal{F}_n$ et $(-1)ˆ0\mathcal{F}_n = \mathcal{F}_n$
Hypothèse de récurrence : au rang k, $\forall n \geq k,\quad \mathcal{F}_n{}\mathcal{F}_{k+1}-\mathcal{F}_k\mathcal{F}_{n+1}=(-1)ˆk\mathcal{F}_{n-k}$
Hérédité (rang k + 1) : $\forall n \geq k+1$

$\mathcal{F}_n\mathcal{F}_{(k+1)+1}-\mathcal{F}_{k+1}\mathcal{F}_{n+1}=\mathcal{F}_n(\mathcal{F}_{k+1}+\mathcal{F}_k) - \mathcal{F}_{k+1}(\mathcal{F}_n+\mathcal{F}_{n-1})$ (Définition de la suite de Fibonacci)

$\mathcal{F}_n\mathcal{F}_{(k+1)+1}-\mathcal{F}_{k+1}\mathcal{F}_{n+1}=-(\mathcal{F}_{n-1}\mathcal{F}_{k+1}-\mathcal{F}_k\mathcal{F}_n)$ (Associativité, commutativité)

$\mathcal{F}_n\mathcal{F}_{(k+1)+1}-\mathcal{F}_{k+1}\mathcal{F}_{n+1}=-(-1)ˆk\mathcal{F}_{n-k-1}$ (Hypothèse de récurrence pour $n-1\,$ et $k\,$ )

$\mathcal{F}_n\mathcal{F}_{(k+1)+1}-\mathcal{F}_{k+1}\mathcal{F}_{n+1}=(-1)ˆ{k+1}\mathcal{F}_{n-(k+1)}$

Propriété 4 : $\forall (p,q)\in\mathbb{N}ˆ2{}, \mathcal{F}_p{}\land{}\mathcal{F}_q = \mathcal{F}_{p{}\land{}q}$

Démonstration

Soient p et q deux entiers naturels. Soit $\delta = p{}\land{}q$ et $\Delta = \mathcal{F}_p\land\mathcal{F}_q$

$p = p'{}\cdot{}\delta$ et $q = q'{}\cdot{}\delta$ par conséquent $\mathcal{F}_\delta{}|{}\mathcal{F}_p$ et $\mathcal{F}_\delta{}|{}\mathcal{F}_q$ (Propriété 2) , d'où nous tirons que $\mathcal{F}_\delta{}|{}\mathcal{F}_p{}\land{}\mathcal{F}_q$ , et par conséquent $\mathcal{F}_\delta{}|{}\Delta$ .

La généralisation du théorème de Bézout nous permet d'affirmer qu'il existe deux entiers naturels a et b ( $a{}\ge{}b$ ) tels que $\delta = a\cdot p - b\cdot q$ ou $\delta = a\cdot q - b\cdot p$ . Supposons que $\delta = a\cdot p - b\cdot q$ (une démonstration analogue peut être faite pour l'autre cas). D'autre part, $\Delta{}|{}\mathcal{F}_p$ et $\Delta{}|{}\mathcal{F}_q$ par conséquent $\Delta{}|{}\mathcal{F}_{a\cdot p}$ et $\Delta{}|{}\mathcal{F}_{b\cdot q}$ (Propriété 2) . Comme $\Delta\,$ en divise aussi toute combinaison linéaire, $\Delta{}|{}\mathcal{F}_{a \cdot p}\mathcal{F}_{b\cdot q + 1} - \mathcal{F}_{b \cdot q}\mathcal{F}_{a\cdot p + 1}$ c'est-à-dire $\Delta{}|{}(-1)ˆ{b\cdot q}\mathcal{F}_{a\cdot pˆ- b\cdot q}$ (Propriété 3) , soit par conséquent $\Delta{}|{}(-1)ˆ{b\cdot q}\mathcal{F}_{\delta}$ c'est à dire $\Delta{}|{}\mathcal{F}_{\delta}$ . Or tout terme de la suite de Fibonacci est positif ou nul, nous en concluons que $\Delta=\mathcal{F}_{\delta}$ .

En particulier, $\forall n\in\mathbb{N}{},\mathcal{F}_n{}\land{}\mathcal{F}_{n+1}=1$ c. -à-d. que $\mathcal{F}_n \perp \mathcal{F}_{n+1}$

Propriété 5 : $\forall n\in\mathbb{N}ˆ*{}, \mathcal{L}_n = \mathcal{F}_{n-1}+\mathcal{F}_{n+1}$

(Précision : les nombres de Lucas $\mathcal{L}_n$ ont même relation de récurrence mais ont pour initialisation $\mathcal{L}_0 = 2$ et $\mathcal{L}_1 = 1$ )

Démonstration

Par récurrence d'ordre 2 sur n

Initialisations

(n = 1) : $\mathcal{L}_1 = 1$ et $\mathcal{F}_0 + \mathcal{F}_2 = 1$

(n = 2) : $\mathcal{L}_2 = 3$ et $\mathcal{F}_1 + \mathcal{F}_3 = 3$

Hypothèses de récurrence :

au rang n, $\mathcal{L}_n = \mathcal{F}_{n-1}+\mathcal{F}_{n+1}$

au rang n+1, $\mathcal{L}_{n+1} = \mathcal{F}_{n}+\mathcal{F}_{n+2}$

Hérédité (rang n + 2) :

$\mathcal{F}_{n+1} + \mathcal{F}_{n+3}=\mathcal{F}_{n}+\mathcal{F}_{n-1}+\mathcal{F}_{n+2}+\mathcal{F}_{n+1}$ (Définition de la suite de Fibonacci)

$\mathcal{F}_{n+1} + \mathcal{F}_{n+3}=(\mathcal{F}_{n-1}+\mathcal{F}_{n+1})+(\mathcal{F}_{n}+\mathcal{F}_{n+2})$ (Associativité, commutativité)

$\mathcal{F}_{n+1} + \mathcal{F}_{n+3}=\mathcal{L}_n+\mathcal{L}_{n+1}$ (Hypothèses de récurrence)

$\mathcal{F}_{n+1} + \mathcal{F}_{n+3}=\mathcal{L}_{n+2}$ (Définition des nombres de Lucas)

Propriété 6 : $\forall n\in\mathbb{N}-\{0,1,2\}{},2\mathcal{L}_n=\mathcal{F}_{n-3}+\mathcal{F}_{n+3}$

Démonstration

$2\mathcal{L}_n = \mathcal{L}_{n+1} - \mathcal{L}_{n-1} + \mathcal{L}_{n+2} - \mathcal{L}_{n+1}$ (définition des nombres de Lucas)

$2\mathcal{L}_n = \mathcal{L}_{n+2} - \mathcal{L}_{n-1}$ (simplification)

$2\mathcal{L}_n = \mathcal{F}_{n+3}+ \mathcal{F}_{n+1} - (\mathcal{F}_{n} + \mathcal{F}_{n-2})$ (Propriété 5)

$2\mathcal{L}_n = \mathcal{F}_{n+3}+ \mathcal{F}_{n} + \mathcal{F}_{n-1} - (\mathcal{F}_{n} + \mathcal{F}_{n-2})$ (Définition de la suite de Fibonacci)

$2\mathcal{L}_n = \mathcal{F}_{n+3}+ \mathcal{F}_{n-3} + \mathcal{F}_{n-2} - \mathcal{F}_{n-2}$ (Simplification, définition de la suite de Fibonacci)

$2\mathcal{L}_n = \mathcal{F}_{n+3}+ \mathcal{F}_{n-3}$ (Simplification)

Propriété 7 : $\forall n\in\mathbb{N}{}, \mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_{n}\mathcal{L}_{n}$

Démonstration

On peut distinguerra deux cas

Pour n = 0 : $\mathcal{F}_0 = 0$ et $\mathcal{F}_0\mathcal{L}_0 = 0$
Pour n > 0,

$\mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_{n+n}$

$\mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_{n-1}\mathcal{F}_n + \mathcal{F}_n\mathcal{F}_{n+1}$ (Propriété 1)

$\mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_n(\mathcal{F}_{n-1} + \mathcal{F}_{n+1})$ (Factorisation)

$\mathcal{F}_{2{}\cdot{}n} = \mathcal{F}_n\mathcal{L}_n$ (Propriété 5)

Propriété 8 : $\forall n\in\mathbb{N}ˆ*{}, \mathcal{F}_{2{}\cdot{}n-1} = \mathcal{F}_{n-1}ˆ2+\mathcal{F}_{n}ˆ2$

par application directe de la propriété 1 pour p = n et q = n -1

Propriété 9 : $\forall n\in\mathbb{N}ˆ*{}, \mathcal{F}_{n+1}\mathcal{F}_{n-1} -\mathcal{F}_nˆ2= (-1)ˆn$ (identité de Cassini)

Démonstration

En remplaçant k par n - 1 dans la propriété 3

$\mathcal{F}_{n}\mathcal{F}_{n} - \mathcal{F}_{n-1}\mathcal{F}_{n+1} = (-1)ˆ{n-1}\mathcal{F}_{1}$

En multipliant par (-1) et en remplaçant $\mathcal{F}_{1}$ par 1

$\mathcal{F}_{n+1}\mathcal{F}_{n-1} - \mathcal{F}_{n}ˆ2 = (-1)ˆ{n}$

Propriété 10 : $\forall n\in\mathbb{N}{},1+\sum_{i=0}ˆn \mathcal{F}_i=\mathcal{F}_{n+2}$

Démonstration

Par récurrence sur n.

Initialisation (n = 0) : $1+\sum_{i=0}ˆ0 \mathcal{F}_i=1$ et $\mathcal{F}_2=1$
Hypothèse de récurrence : au rang n, $1+\sum_{i=0}ˆn \mathcal{F}_i=\mathcal{F}_{n+2}$
Hérédité (rang n + 1) :

$1+\sum_{i=0}ˆ{n+1} \mathcal{F}_i=1+\sum_{i=0}ˆn \mathcal{F}_i+\mathcal{F}_{n+1}$ (Calcul sur les sommes)

$1+\sum_{i=0}ˆ{n+1} \mathcal{F}_i=\mathcal{F}_{n+1}+\mathcal{F}_{n+2}$ (Hypothèse de récurrence)

$1+\sum_{i=0}ˆ{n+1} \mathcal{F}_i=\mathcal{F}_{(n+1)+2}$ (Définition de la suite de Fibonacci)

Propriété 11 : $\forall n\in\mathbb{N}{},1+\sum_{i=0}ˆn \mathcal{F}_{2{}\cdot{}i}=\mathcal{F}_{2{}\cdot{}n+1}$

Démonstration

Par récurrence sur n

Initialisation (n = 0) : $1+\sum_{i=0}ˆ0 \mathcal{F}_{2{}\cdot{}i}=1$ et $\mathcal{F}_1=1$
Hypothèse de récurrence : au rang n, $1+\sum_{i=0}ˆn \mathcal{F}_{2{}\cdot{}i}=\mathcal{F}_{2{}\cdot{}n+1}$
Hérédité (rang n + 1) :

$1+\sum_{i=0}ˆ{n+1} \mathcal{F}_{2{}\cdot{}i}=1+\sum_{i=0}ˆn \mathcal{F}_{2{}\cdot{}i}+\mathcal{F}_{2{}\cdot{}n+2}$ (Calcul sur les sommes)

$1+\sum_{i=0}ˆ{n+1} \mathcal{F}_{2{}\cdot{}i}=\mathcal{F}_{2{}\cdot{}n+1}+\mathcal{F}_{2{}\cdot{}n+2}$ (Hypothèse de récurrence)

$1+\sum_{i=0}ˆ{n+1} \mathcal{F}_{2{}\cdot{}i}=\mathcal{F}_{2{}\cdot{}(n+1)+1}$ (Définition de la suite de Fibonacci)

Propriété 12 : $\forall n\in\mathbb{N}{},\mathcal{F}_{n+1} = \sum_{k=0}ˆ{\infty} {n-k \choose k}$ où les $n-k \choose k$ sont des cœfficients binomiaux.

Démonstration

En réalité, la somme n'est pas illimitée car l'ensemble des $n-k \choose k$ sont nuls pour k > n - k mais on sommera sur $\infty$ pour favoriser les démonstrations.

Par récurrence d'ordre 2 sur n.

Initialisation

(n = 0) : $\sum_{k=0}ˆ{\infty} {0-k\choose k} = 1$ et $\mathcal{F}_1 = 1$

(n = 1) : $\sum_{k=0}ˆ{\infty} {1-k\choose k} = 1$ et $\mathcal{F}_2 = 1$

Hypothèses de récurrence :

au rang n, $\mathcal{F}_{n+1} = \sum_{k=0}ˆ{\infty} {n - k \choose k}$

au rang n + 1, $\mathcal{F}_{n+2} = \sum_{k=0}ˆ{\infty} {n +1 - k \choose k}$

Hérédité (rang n + 2) :

$\sum_{k=0}ˆ{\infty} {(n+2)-k \choose k} = \sum_{k=0}ˆ{\infty} {(n+1) - k \choose k} + {(n+1) - k \choose k-1}$

(Formule du triangle de Pascal)

$\sum_{k=0}ˆ{\infty} {(n+2)-k \choose k} = \sum_{k=0}ˆ{\infty} {(n+1) - k \choose k} + \sum_{k=1}ˆ{\infty}{n - (k - 1) \choose k-1}$

Car ${n+1 \choose -1} = 0$ )

$\sum_{k=0}ˆ{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+2}+\sum_{m=0}ˆ{\infty}{n - m \choose m}$

(Hypothèse de récurrence, changement de variable $m = k - 1\,$ )

$\sum_{k=0}ˆ{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+2}+ \mathcal{F}_{n+1}$ (Hypothèse de récurrence)

$\sum_{k=0}ˆ{\infty} {(n+2)-k \choose k} = \mathcal{F}_{n+3}$ (Définition de la suite de Fibonacci)

Cela veut dire que, dans un triangle de Pascal, les nombres de Fibonacci s'obtiennent en sommant les termes localisés sur une diagonale (du bas vers la droite)

Propriété 13 : $\forall n\in\mathbb{N}ˆ*,\varphiˆn = \mathcal{F}_n{}\cdot{}\varphi + \mathcal{F}_{n-1}$

Démonstration

Par récurrence sur $n\,$

Initialisation ( $n = 1\,$ ) : $\varphiˆ1 = \mathcal{F}_1{}\cdot{}\varphi + \mathcal{F}_0$
Hypothèse de récurrence : au rang $n\,$ , $\varphiˆn = \mathcal{F}_n{}\cdot{}\varphi + \mathcal{F}_{n-1}$
Hérédité (rang $n + 1\,$ ) :

$\varphiˆ{n+1}= \varphi{}\cdot{}\varphiˆn$ (Calculs sur les puissances)

$\varphiˆ{n+1} =\varphi{}\cdot{}(\mathcal{F}_n{}\cdot{}\varphi + \mathcal{F}_{n-1})$

$\varphiˆ{n+1}=\varphiˆ2\mathcal{F}_n+\varphi\mathcal{F}_{n-1}$ (Distributivité)

$\varphiˆ{n+1}=(1+\varphi)\mathcal{F}_n+\varphi\mathcal{F}_{n-1}$ (Hypothèse de récurrence appliquée au cas $n = 2\,$ )

$\varphiˆ{n+1}=\varphi(\mathcal{F}_{n-1}+\mathcal{F}_n)+\mathcal{F}_n$ (Factorisation)

$\varphiˆ{n+1}=\mathcal{F}_{n+1}{}\cdot{}\varphi+\mathcal{F}_n$ (Définition de la suite de Fibonacci)

Propriété 14 : $<img class=$

Démonstration

Il suffit de remplacer $\mathcal{F}_n$ par son expression selon $\varphi$ et $\varphi'$ , et de simplifier l'expression.

Formules closes

La formule suivante sert à retrouver l'ensemble des nombres de Fibonacci (formule de Binet) :

$\forall n \in \mathbb{Z}, \mathcal{F}_{n} = \frac{1}{\sqrt{5}} (\varphiˆn - \varphi'ˆn) = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)ˆ{n} - \left( \frac{1 - \sqrt{5}}{2} \right)ˆ{n} \right]$

La formule suivante sert à retrouver l'ensemble des nombres de Lucas (formule de Maillet) :

$\forall n \in \mathbb{Z}, \mathcal{L}_{n} = \varphiˆn + \varphi'ˆn = \left( \frac{1 + \sqrt{5}}{2} \right)ˆ{n} + \left( \frac{1 - \sqrt{5}}{2} \right)ˆ{n}$

Bestiaire de formules

$N \ge 1, \mathcal{F}_{2N+1} = 4ˆN\cdot\prod_{n=1}ˆ{N}\left (\cosˆ2\left(\frac{n\pi}{2N+1}\right)+\frac{1}{4}\right )$

Primalité des nombres de Fibonacci

On ignore s'il existe une illimitété de nombres de Fibonacci premiers. On sait que $\mathcal{F}_n$ divise $\mathcal{F}_{k{}\cdot{}n}$ (voir Propriétés, Propriété 2), et par conséquent que, pour tout $<img class=$ est premier, alors $n\,$ est premier, mais la réciproque est fausse. Le plus grand nombre de Fibonacci premier connu à ce jour (avril 2009) est $\mathcal{F}_{1636007}$ qui possède 341905 chiffres.

Depuis 1964, on connait des suites $(\mathcal{T}_n)$ vérifiant en même temps les trois conditions suivantes :

$\mathcal{T}_{n+2}=\mathcal{T}_{n+1}+\mathcal{T}_n$
$\mathcal{T}_n{}$ et $\mathcal{T}_{n+1}$ sont premiers entre eux (ils n'ont aucun diviseur commun).
$\forall n\in\mathbb{N},\; \mathcal{T}_n$ n'est pas premier.

Par exemple :

suite A082411 de l'ŒIS (John Nicol, 1999) déterminée par :
- $\mathcal{T}_0 = 407389224418$
- $\mathcal{T}_1 = 76343678551$
suite A083216 de l'ŒIS (Herbert Wilf, 1990) déterminée par :
- $\mathcal{T}_0 = 20615674205555510 = 2\cdot 5\cdot 5623\cdot 366631232537$
- $\mathcal{T}_1 = 3794765361567513 = 3\cdot 1264921787189171$
et suite A083103 de l'ŒIS (Robert Graham, 1964; non vérifiée, selon l'ŒIS) déterminée par :
- $\mathcal{T}_0 = 1786772701928802632268715130455793 = 2521\cdot 49993\cdot 14177095479037851751198481$
- $\mathcal{T}_1 = 1059683225053915111058165141686995 = 3\cdot 5\cdot 84089\cdot 73919059\cdot 150031897\cdot 75754002239$

Applications

En poésie, un fib est un petit poème, sorte de haïku, dont le nombre de pieds des premiers vers correspond aux premiers nombres de la suite (1, 1, 2, 3, 5, 8).

La suite de Fibonacci apparaît dans de nombreux problèmes de dénombrement. A titre d'exemple, le terme d'indice n (pour n supérieur ou égal à 2) de la suite de Fibonacci sert à dénombrer le nombre de façons de parcourir un chemin de longueur n-1 en faisant des pas de 1 ou 2. Ce problème apparaît d'aillleurs particulièrement tôt en Inde, sous le nom maatraameru (montagne de cadence), dans le travail du grammairien de sanskrit Pingala, le Chhandah-shastra, (l'art de la Prosodie), 450 ou 200 av. J. -C. ). Le mathématicien indien Virahanka en a donné des règles explicites au VIII^e siècle. Le philosophe indien Hemachandra (c. 1150) (et aussi Gopala) ont revisité le problème de manière assez détaillée. En sanskrit en effet, les voyelles peuvent être longues (L) ou courtes (C), et Hemachandra a souhaité calculer combien on peut former de cadences différentes d'une longueur donnée, chaque cadence étant définie par les longueurs des voyelles qui la forment. Si la voyelle longue est deux fois plus longue que la courte, les solutions sont , selon la longueur totale de la cadence :

1 C → 1

2 CC, L → 2

3 CCC, CL, LC → 3

4 CCCC, CCL, CLC, , LCC, LL → 5

5 CCCCC, CCCL, CCLC, CLCC, LCCC, CLL, LCL, LLC → 8

Le nombre de cadences fait apparaître les termes de la suite de Fibonacci. En effet, une cadence de longueur n peut être constituée en ajoutant C à une cadence de longueur n-1, ou L à une cadence de longueur n-2. Ainsi le nombre de cadences de longueur n est la somme des deux nombres qui ont précédé de la série. Ce problème est aussi équivalent au dénombrement des emballages de longueur n donnée, constitué d'articles de longueur 1 ou 2, tel qu'on le trouve par exemple dans The Art of Computer Programming de Donald Knuth.

Les nombres de Fibonacci interviennent dans l'étude de l'exécution de l'algorithme d'Euclide qui détermine le plus grand commun diviseur de deux entiers.

Matiyasevich a montré que les nombres de Fibonacci pouvaient être définis par une équation diophantienne, ce qui a conduit à la résolution du dixième problème d'Hilbert. En 1975, Jones en a déduit que, pour des valeurs de x et y entières positives ou nulles, les valeurs positives du polynôme $2 x y 4 + x 2 y 3 - 2 x 3 y 2 - y 5 - x 4 y + 2 y$ étaient précisément les nombres de Fibonacci. Ces valeurs positives s'obtiennent d'ailleurs en attribuant pour valeurs à x et y deux nombres de Fibonacci successifs.

Les nombres de Fibonacci apparaissent dans la formule des diagonales du triangle de Pascal (voir Propriétés, Propriété 11).

Une utilisation intéressante des suites de Fibonacci est la conversion des miles en kilomètres. A titre d'exemple, pour savoir combien de kilomètres font 5 miles, il suffit de considérer le $\mathcal{F}_5 = 5$ et le suivant $\mathcal{F}_6 = 8$ . 5 miles font à peu près 8 kilomètres. Cela fonctionne parce que le facteur de conversion des miles aux kilomètres, à peu près 1, 609, est grossièrement égal à $\varphi\,$ ,

Carrés de Fibonacci en spirale.

Une bonne approximation d'un rectangle d'or peut être construite avec carrés dont les côtés sont égaux aux nombres de Fibonacci.

Une spirale logarithmique peut être approchée de la manière suivante : on commence à l'origine d'un repère cartésien, on se déplace de $\mathcal{F}_1$ unités vers la droite, puis de $\mathcal{F}_2$ unités vers le haut, on se déplace de $\mathcal{F}_3$ unités vers la gauche, ensuite de $\mathcal{F}_4$ unités vers le bas, puis de $\mathcal{F}_5$ unités vers la droite, etc. Cela est comparable à la construction mentionnée dans l'article sur le nombre d'or. Les nombres de Fibonacci apparaissent fréquemment dans la nature quand des spirales logarithmiques sont construites à partir d'une unité discrète, telles que dans les tournesols ou dans les pommes de pin. Depuis l'antiquité grecque, la suite est aussi utilisée par les architectes pour définir l'agencement et les proportions des différentes pièces d'un logement.

La plupart des êtres vivants sexués sont issus de deux parents, de sorte que leurs ancêtres à la n^e génération, supposés différents, sont au nombre de 2ⁿ. Mais les hyménoptères sont tels que les femelles sont issues de deux parents, et les mâles sont issus d'une mère uniquement. Il en résulte que leurs ancêtres à la n^e génération sont constitués :

pour les femelles, de $\mathcal F_n$ mâles et $\mathcal F_{n+1}$ femelles,

pour les mâles, de $\mathcal F_{n-1}$ mâles et $\mathcal F_n$ femelles.

Le nombre de façons différentes de paver un rectangle 2×N au moyen de dominos 2×1 est $\mathcal F_{N+1}$ .

Démonstration

Par récurrence sur N qu'on considéra comme la longueur horizontale du rectangle 2×N :

Initialisation :

Le rectangle 2×1 est un domino 2×1 ; il y a 1 seule façon de paver ce rectangle $\left( 1=\mathcal F_2 \right)$ .
Supposons qu'il y ait $\mathcal F_{N+1}$ façons de paver le rectangle 2×N.
Considérons le rectangle 2× :
- Ce rectangle 2× (N+1) peut être construit comme la juxtaposition d'un rectangle 2× (N-1) et de 2 dominos positionnés horizontalement (la longueur du rectangle d'origine est toujours N+1) ; il y a par hypothèse $\mathcal F_N$ façons de paver le rectangle auquel on a retiré les 2 dominos.
- Ce rectangle 2× (N+1) peut aussi être construit comme la juxtaposition d'un rectangle 2×N et d'un domino positionné verticalement (la longueur du rectangle d'origine est toujours N+1) ; il y a par hypothèse $\mathcal F_{N+1}$ façons de paver le rectangle auquel on a retiré le domino.
- Le nombre de façons de paver le rectangle 2× (N+1) est par conséquent la somme $\mathcal F_{N} + \mathcal F_{N+1} = \mathcal F_{N+2}$ , ce qui termine le raisonnement par récurrence.

Généralisations

Il existe plusieurs voies pour généraliser la suite de Fibonacci : on peut modifier les valeurs initiales, modifier les cœfficients de la relation de récurrence ou modifier le nombre de termes (ou ordre) de la relation de récurrence.

Suites de Fibonacci généralisées

On nomme suite de Fibonacci généralisée toute suite définie par la même relation de récurrence que la suite de Fibonacci, mais dont les termes initiaux sont différents de 0 et 1. Sur le modèle de la démonstration donnée plus haut (voir section Expression fonctionnelle), une telle suite est une combinaison linéaire des deux suites géométriques $(\varphi)ˆn$ et $(1-\varphi )ˆn$ où $\varphi\,$ est le nombre d'or. Le quotient de deux termes consécutifs tend toujours vers $\varphi\,$ .

Parmi ces suites de nombres, il faut signaler les nombres de Lucas obtenus en choisissant comme initialisation : $\mathcal{L}_0 =2$ et $\mathcal{L}_1=1$ . Cela donne la suite 2, 1, 3, 4, 7, 11, 18, 29, … On trouve quelquefois une initialisation $\mathcal{L}_0 =1$ et $\mathcal{L}_1=3$ qui ne consiste qu'à décaler la suite d'un rang. Ces nombres interviennent dans la résolution d'équations diophantiennes. Ils sont particulièrement liés suite à Fibonacci, surtout par la relation suivante : $\mathcal{L}_n = \mathcal{F}_{n+1} + \mathcal{F}_{n-1}\,$ pour tout entier n strictement positif (voir Propriétés, Propriété 5).

Suites de Lucas

Ce sont les suites où la relation de récurrence a changé : elle est devenue

$U_{n+2} = P \cdot U_n + Q \cdot U_{n+1}$

Elles sont de deux types selon que l'initialisation est de $u 0 = 0$ et $u 1 = 1$ ou qu'elle est $v 0 = 2$ et $v 1 = P$ .

La suite de Fibonacci est alors une suite u de Lucas de paramètres P = 1 et Q = 1. La suite des nombres de Lucas est alors une suite v de Lucas de paramètres $P = 1$ et $Q = 1$ .

Articles détaillés : Suite de Lucas et Nombre de Lucas.

Suites de k-bonacci

Ce sont des suites dont la relation de récurrence est d'ordre k. Un terme est la somme des k termes qui le précèdent

$u_{n+k} \, = \, u_n + u_{n+1} + u_{n+2} + \dots +u_{n+k - 1}$

Parmi ces suites, on distingue la suite de Tribonacci (récurrence d'ordre 3) et la suite de Tetranacci (récurrence d'ordre 4). Selon ce nouveau classement de suites, la suite de Fibonacci est une suite de 2-bonacci.

Si on modifie tout à la fois (initialisation, récurrence, ordre) on arrive à la totalité particulièrement général des suites à récurrence linéaire.

Voir aussi

N. Vorobiev, Caractères de Divisibilité, Suite de Fibonacci, coll. Initiation aux Mathématiques, Editions Mir, Moscou, 1973

La suite de Fibonacci dans la culture populaire

Littérature

Da Vinci Code de Dan Brown

Cinéma

Crimes à Oxford
Las Vegas 21

Télévision

Numb3rs (épisode 21 de la saison 5)
Fringe (saison 1)
Chuck (épisode 7 de la saison 2)
Alias

Liens externes

Divisibilité des nombre de Fibonacci
Suite de Fibonacci et nombre d'or dans la totalité de Mandelbrot
Suite de Fibonacci dans le dictionnaire des nombres
Les suites de Fibonacci aléatoires, conférence de Benoît Rittaud à la Cité des sciences et de l'industrie
(en) Théorème de Zeckendorf

Suite de Fibonacci

La suite de Fibonacci est une suite d'entiers particulièrement connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, décrit...

Catégories :

Page(s) en rapport avec ce sujet :

Présentation mathématique

Formule de récurrence

Nombres de Fibonacci

Expression fonctionnelle

La suite pour les nombres négatifs

Limite des quotients

Bases et espaces vectoriels

Algorithmes de calcul des nombres de Fibonacci

Avec la formule de Binet

Algorithme récursif naïf

Algorithme linéaire

Algorithme logarithmique

Curiosité algorithmique

Propriétés de la suite de Fibonacci

Formules closes

Bestiaire de formules

Primalité des nombres de Fibonacci

Applications

Généralisations

Suites de Fibonacci généralisées

Suites de Lucas

Suites de k-bonacci

Voir aussi

La suite de Fibonacci dans la culture populaire

Littérature

Cinéma

Télévision

Liens externes

Recherche sur Amazon (livres) :