Formule générale
Tout le monde connaît la relation de récurrence définissant la suite de Fibonacci :
$$F_{n+2} = F_{n+1} + F_n,$$ mais la formule générale pour $F_n$ est bien moins connue. Au vu du point théorique précédent concernant les suites linéaires récurrentes, et comme il s'agit ici d'une suite linéaire récurrente d'ordre $2$, il est cependant certain qu'une formule existe bel et bien pour $F_n$. Cela peut sembler étrange : si une formule simple existait, alors la suite de Fibonacci semblerait bien moins intéressante ! Voyons ce qu'il en est.
Le polynôme caractéristique associé à la suite de Fibonacci est
$$P(x) = x^2 - x - 1.$$ Le discriminant de ce polynôme est $\Delta = 1^2 -4 \cdot 1 \cdot (-1) = 5$ et les racines de $P$ sont donc
$$\frac{1 + \sqrt{5}}{2} \quad \text{et} \quad \frac{1 - \sqrt{5}}{2}.$$ Les polynômes $Q_1$ et $Q_2$ intervenant dans la méthode doivent donc être de degré $0$, d'où il existe $A, B \in \mathbb{C}$ tels que
$$F_n = A \cdot \left(\frac{1+\sqrt{5}}{2}\right)^n + B \cdot \left(\frac{1-\sqrt{5}}{2}\right)^n.$$ Pour déterminer $A$ et $B$, on utilise $F_0 = 0$ et $F_1 = 1$, ce qui nous donne
$$\left\{\begin{align}
0 = F_0 &= A+B \\[1mm]
1 = F_1 &= A \cdot \left(\frac{1+\sqrt{5}}{2}\right) + B \cdot \left(\frac{1-\sqrt{5}}{2}\right)
\end{align}\right.$$ On a donc $B = -A$ et en substituant dans la deuxième égalité on a
$$\begin{align}
& A \cdot \left(\frac{1+\sqrt{5}}{2}\right) -A \cdot \left(\frac{1-\sqrt{5}}{2}\right) = 1 \\[1mm]
\Leftrightarrow \ & A \cdot \sqrt{5} = 1 \\[1mm]
\Leftrightarrow \ & A = \frac{1}{\sqrt 5}
\end{align}$$ On a donc la formule finale suivante, appelée
formule de Binet :
Formule de Binet
$$F_n = \frac{1}{\sqrt 5} \cdot \left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right).$$
On comprend mieux pourquoi cette formule est méconnue : elle n'est pas réellement jolie et ne permet donc pas de s'en faire une grande intuition. On peut d'ailleurs regretter l'apparition de $\sqrt{5}$ dans celle-ci : nous savons par définition que $F_n$ sera toujours un nombre entier, mais la formule générale fait pourtant intervenir un nombre irrationnel. Cette formule va cependant nous permettre de trouver certaines propriétés intéressantes de la suite de Fibonacci.
Nombre d'or dans la suite de Fibonacci
Le nombre d'or est généralement défini comme le rapport $\frac{a}{b}$ entre deux longueurs $a > b$ tel que le rapport entre la somme des deux longueurs et la plus grande soit égal au rapport entre la plus grande et la plus petite. Autrement dit, $a$ et $b$ doivent vérifier $a > b$ et
$$\frac{a+b}{a} = \frac{a}{b}.$$ Le nombre d'or est alors simplement $\phi = \frac{a}{b} > 1$, et il est facile de trouver sa valeur puisqu'en remplaçant $a$ par $\phi \cdot b$ dans l'équation précédente on obtient
$$ \begin{align}
& \frac{\phi+1}{\phi} = \phi \\[1mm]
\Leftrightarrow \ & \phi^2 - \phi - 1 = 0
\end{align}$$ Les solutions sont donc les racines du polynôme $P(x) = x^2 - x - 1$ qui est exactement le polynôme caractéristique relatif à la suite de Fibonacci. Nous avions calculé les deux racines, et le nombre d'or est celle d'entre-elle qui est supérieure à $1$ :
$$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618034$$ On peut en fait facilement remarquer que l'autre racine est égale à $-\phi^{-1}$. Ceci nous donne une formule un peu plus compacte pour $F_n$ :
Formule de Binet (avec le nombre d'or)
$$F_n = \frac{1}{\sqrt 5} \left(\phi^n - (-\phi)^{-n}\right).$$
En fait, vu que $\phi > 1$, le terme $(-\phi)^{-n}$ dans cette formule tend très rapidement vers $0$. Cela signifie que pour $n$ assez grand, on a
$$F_n \approx \frac{\phi^n}{\sqrt{5}}.$$ En fait, les premières valeurs de la suite $\displaystyle\left(\frac{\phi^n}{\sqrt{5}}\right)$ sont (arrondies à deux décimales après la virgule) :
$$0.45, 0.72, 1.17, 1.89, 3.07, 4.96, 8.02, 12.98, 21.01, 33.99, 55.00, \ldots$$ ce qui se rapproche ostensiblement des vraies valeurs de $(F_n)$ :
$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$$ Une conséquence assez connue de cette constatation est que le quotient de deux nombres de Fibonacci consécutifs tend vers le nombre d'or (plus on va loin dans la suite) :
$$\frac{F_{n+1}}{F_n} \to \phi.$$