Nombres de Fibonacci

La suite de Fibonacci est une séquence mathématique infinie dans laquelle chaque terme est la somme des deux termes précédents, commençant généralement par 0 et 1.

La suite commence ainsi 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, et ainsi de suite.

Les nombres de la suite de Fibonacci, noté $ F_n $ ou $ F(n) $ sont égaux à la somme des deux termes précédents, ils suivent donc la formule de récurrence : $$ F(n) = F(n-1) + F(n-2) $$ qui peut aussi s'écrire $$ F(n+2) = F(n) + F(n+1) $$

Pour initialiser la suite, par défaut, les deux premiers termes (appelés graines) sont $ F(0) = 0 $ et $ F(1) = 1 $

La formule de Binet permet de calculer le n-ième terme sans avoir à utiliser la récursion ni devoir calculer les termes précédents. La formule est $$ F(n) = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n $$ et fait intervenir le nombre d'or.

Les premiers nombres de la suite de Fibonacci sont :

Pour les termes de Fibonacci suivants, utiliser le calculateur ci dessus.

Chaque terme de la séquence est égal au précédent multiplié par environ $ \varphi = 1.618 $ (nombre d'or).

Le problème de croissance des lapins est un problème proposé par Leonardo Fibonacci vers 1200.

En prenant un couple de lapins (male + femelle), chaque mois, un couple se reproduit et donne naissance à un nouveau couple qui à son tour peut se reproduire au bout de 2 mois. Combien de lapins seront nés au bout de X mois ?

Au commencement il y a 1 couple, puis

Chaque mois, le nombre total de lapins est égal à la somme des nombres des 2 mois précédents puisqu'il s'agit du nombre de lapins existant (ceux du mois précédent) additionné du nombre de bébés des lapins nés des couples qui ont au moins deux mois (donc le nombre de lapins il y a 2 mois). Les nombres trouvés sont les nombres de la suite de Fibonacci.

La suite de Lucas est similaire à la suite de Fibonacci, mais elle commence par 2 et 1 (au lieu de 0 et 1). Les formules de récurrence sont les mêmes.

Un code source pour programmer le calcul des nombres de Fibonacci par récurrence : //Pseudo-code
function fibonacci(n) {
if (n == 0) return 0
if (n == 1) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}

Et une version itérative de l'algorithme ://Pseudo-code
function fibonacci(n) {
if (n == 0) return 0
if (n == 1) return 1
prev = 0
curr = 1
for i from 2 to n {
next = prev + curr
prev = curr
curr = next
}
return curr
}