La suite de Fibonacci est l’une des notions les plus citées en prépa ECG/ECT : au-delà de sa définition habituelle et de son lien avec le nombre d’or, cette suite est souvent présente dans les sujets de concours sous diverses formes. On abordera les démonstrations qui peuvent tomber et comment on la mobilise en pratique : une preuve par récurrence rédigée comme devant un jury HEC, une interprétation combinatoire directement rattachée au chapitre dénombrement, et une vraie analyse algorithmique pour Python.
Définition et premiers termes de la suite de Fibonacci
La suite de Fibonacci \((F_n)_{n \in \mathbb{N}}\) est définie par :\(F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ pour } n \geq 2.\)
Les premiers termes : \((0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots)\)
C'est une suite récurrente linéaire d'ordre 2 à coefficients constants, une catégorie centrale dans le programme de mathématiques ECT et ECG (mathématiques appliquées comme approfondies).
La formule explicite de la suite de Fibonacci
L'équation caractéristique associée à cette récurrence double est \(r^2 - r - 1 = 0\) (cours sur les récurrences doubles) et les racines associés sont : \(\varphi_1 = \frac{1+\sqrt5}{2} \approx 1{,}618\) (c'est le nombre d'or) et \(\varphi_2 = \frac{1-\sqrt5}{2} \approx -0{,}618.\)
On remarque que \(\varphi_1 + \varphi_2 = 1\) et \(\varphi_1 .\varphi_2 = -1\) deux relations qu'on réutilisera plus loin.
La solution générale s'écrit \(F_n = A\varphi_1^n + B\varphi_2^n\) avec A et B des constantes.
Grâce aux conditions initiales \(F_0=0\), \(F_1=1\) on a \(A = \frac{1}{\sqrt5}, B = -\frac{1}{\sqrt5}\)
D'où la formule explicite pour les termes de la suite de Fibonacci : \(F_n = \frac{\varphi_1^n - \varphi_2^n}{\sqrt5}.\) connue sous le nom de formule de Binet
La démonstration par récurrence, la rédaction attendue
Voici une rédaction propre de la démonstration de l'identité par récurrence, ce fondamental est à savoir dès la première année en classe préparatoire et peut très bien tomber en khôlle et aux oraux en question sans préparation.
Démontrons par récurrence que, pour tout \(n \geq 1\) : \(\sum_{k=1}^{n} F_k = F_{n+2} - 1.\) \((\mathcal{H}(n))\)
Initialisation. Pour n=1 :
\(\sum_{k=1}^{1} F_k = F_1 = 1\), et \(F_3 - 1 = 2 - 1 = 1\). L'égalité est vérifiée.
Hérédité. Soit \(n \geq 1\) fixé. Supposons l'hypothèse de récurrence \(\mathcal{H}(n)\) : \(\sum_{k=1}^{n} F_k = F_{n+2}-1\) vraie, et montrons \(\mathcal{H}(n+1)\).
\(\sum_{k=1}^{n+1} F_k = \left(\sum_{k=1}^{n} F_k\right) + F_{n+1} \overset{\mathcal{H}(n)}{=} (F_{n+2}-1) + F_{n+1} = (F_{n+1}+F_{n+2}) - 1 = F_{n+3} - 1\) en utilisant la relation de récurrence \(F_{n+3} = F_{n+2}+F_{n+1}\) à la dernière étape.
On a donc \(\mathcal{H}(n+1)\) vraie.
Conclusion. D'après le principe de récurrence, \(\mathcal{H}(n)\): \(\sum_{k=1}^{n} F_k = F_{n+2}-1\) est vraie pour tout \(n \geq 1\).
Lire plus : Matrices ECT: 2 récurrences clés aux concours
Retrouver la formule de Binet par les séries entières
Posons la série génératrice de la suite : \(G(x) = \sum_{n \geq 0} F_n x^n.\)
En utilisant la relation de récurrence pour \((n \geq 2)\) et le fait que \(F_0 = 0, F_1 = 1\) :
\(G(x) - x = \sum_{n \geq 2} F_n x^n = \sum_{n \geq 2} (F_{n-1} + F_{n-2}) x^n = x.G(x) + x^2.G(x)\)D'où \(G(x)(1 - x - x^2) = x\), soit : \(G(x) = \frac{x}{1 - x - x^2}\) (*)
Or \((1 - x - x^2)\) se factorise exactement avec les racines \(\varphi_1\) et \(\varphi_2\) trouvées plus haut, car \((1-\varphi_1x)(1-\varphi_2x) = 1 - (\varphi_1+\varphi_2)x + \varphi_1\varphi_2 x^2 = 1 - x - x^2\) (on utilise ici les deux relations notées en partie 2)
En injectant cette dernière égalité dans (*) : \(G(x) = \frac{x}{(1-\varphi_1x)(1-\varphi_2x)} = \frac{1}{\sqrt5}\left(\frac{1}{1-\varphi_1 x} - \frac{1}{1-\varphi_2 x}\right).\)
Chaque fraction est le développement en série entière d'une fonction géométrique (on reconnait le \(\frac{1}{1-\lambda x}\)) , de rayon de convergence respectif \(\frac{1}{|\varphi_1|}\) et \(\frac{1}{|\varphi_2|}\).
En développant chaque fraction : \(G(x) = \frac{1}{\sqrt5} \sum_{n\geq 0} (\varphi_1^n - \varphi_2^n) x^n.\)
Par unicité du développement en série entière, on identifie terme à terme avec \(G(x) = \sum F_n x^n\) et on retrouve, sans passer par l'équation caractéristique, la formule de Binet.
L'intérêt de cette démonstration est qu'elle peut se généraliser à n'importe quelle suite récurrente linéaire, les concepteurs peuvent tout à fait penser un exercice guidé de ce type qui démontre cette formule de Binet.
Une autre démonstration de la formule de Binet qui allie suite et matrice — méthode à connaître.
On pose \(M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\), qui vérifie \(\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = M^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}\). Les valeurs propres de \(M\) sont précisément \(\varphi_1\)et \(\varphi_2\). On va chercher à identifier la matrice diagonalisable puis obtenir une expression explicite du terme général sans refaire l'équation caractéristique.
Vecteurs propres. Pour une valeur propre \(\lambda \in \{\varphi_1, \varphi_2\}\), on résout \(Mv = \lambda v\) avec \(v=\begin{pmatrix} x \\ y \end{pmatrix}\) : la première ligne donne \(x+y=\lambda x\), soit \(y = (\lambda-1)x\). En prenant \(x=1\) et en utilisant la relation \(\varphi_1+\varphi_2=1\) (donc \(\varphi_1 - 1 = -\varphi_2\) et \(\varphi_2-1=-\varphi_1\)), on obtient des vecteurs propres relativement simples : \(v_{\varphi_1} = \begin{pmatrix}1 \\ -\varphi_2\end{pmatrix}, \qquad v_{\varphi_2} = \begin{pmatrix}1 \\ -\varphi_1\end{pmatrix}.\)
Décomposition du vecteur initial dans la base propre. Plutôt que de passer par la méthode \(PMP^{-1} = PDP^{-1}\), la méthode la plus rapide consiste à décomposer directement \(\binom{1}{0}\) sur la base de vecteurs propres \((v_{\varphi_1}, v_{\varphi_2})\) :
on cherche \(a, b\) tels que \(\binom{1}{0} = a\,v_{\varphi_1} + b\,v_{\varphi_2}\). Le système \(a+b=1\), \(a\varphi_2+b\varphi_1=0\) se résout en \(a = \frac{\varphi_1}{\sqrt5}\), \(b = -\frac{\varphi_2}{\sqrt5}\) (en utilisant à nouveau \(\varphi_1-\varphi_2=\sqrt5\)).
Conclusion. Comme \(v_{\varphi_1}\) et \(v_{\varphi_2}\)sont des vecteurs propres, \(M^n\) agit sur chacun par simple multiplication par \(\varphi_1^n\), resp. \(\varphi_2^n\) (c'est la récurrence à savoir démontrer \(M^n u = \lambda^n u\))\(M^n \begin{pmatrix}1\\0\end{pmatrix} = \frac{\varphi_1^{n+1}}{\sqrt5} v_{\varphi_1} - \frac{\varphi_2^{n+1}}{\sqrt5} v_{\varphi_2}.\)
En ne regardant que la seconde coordonnée (celle qui donne \(F_n\)), et en utilisant \(\varphi_1\varphi_2=-1\) pour simplifier \(-\varphi_1^{n+1}\varphi_2 + \varphi_2^{n+1}\varphi_1\)en \(\varphi_1^n - \varphi_2^n\) : \(F_n = \frac{\varphi_1^n - \varphi_2^n}{\sqrt5}\), exactement la formule de Binet, retrouvée cette fois par diagonalisation .
Au-delà de Fibonacci, c'est la méthode générale à retenir pour toute suite vectorielle \(u_{n+1} = A.u_n\) avec \(u_n = \binom{a_n}{b_n}\)associée à une matrice diagonalisable \(A\):
- Diagonaliser \(A\) et poser \(u_0\)
- Au lieu de construire \(P\) puis l'inverser, chercher directement les coefficients \(a, b\) tels que \(u_0 = a\,v_1 + b\,v_2\) — système à deux équations, deux inconnues.
- Comme \(v_1, v_2\) sont vecteurs propres, \(A^n u_0 = a\lambda_1^n v_1 + b\lambda_2^n v_2\) directement
Lire plus : Inverser une matrice 2×2 : cours, méthode et exemples
Le lien entre Fibonacci et le dénombrement
Fibonacci ne sert pas qu'à calculer : Combien existe-t-il de façons de paver une bande de longueur \(n\) à l'aide de carrés \(1\times1\) et de dominos \(1\times2\)? Notons \(T(n)\) ce nombre.
On pose les conditions suivantes sur la dernière pièce posée : si c'est un carré, il reste \(T(n-1)\) façons de paver le reste ; si c'est un domino, il en reste \(T(n-2)\). D'où \(T(n) = T(n-1)+T(n-2)\), avec\(T(0)=1\) (pavage vide) et \(T(1)=1\)on retrouve la récurrence de Fibonacci, décalée d'un indice : \(T(n) = F_{n+1}\).
Cette exercice rattache Fibonacci au chapitre dénombrement plutôt qu'à la seule récurrence.
Applications Python
La programmation de la suite de Fibonacci est un grand classique, que ce soit pour les concours d'entrée aux écoles de commerce ou pour vos futurs entretiens, comme en finance de marché notamment. Voici trois implémentations, avec leur complexité réelle.
Version récursive - la plus facile mais pas parfaite:
def fib_recur(n):
if n <= 1:
return n
return fib_recur(n - 1) + fib_recur(n - 2)
// si n > 1 on affiche retourne \(F_n\) en fonction de \(F_{n-1}\) et \(F_{n-2}\)
Chaque appel en déclenche deux autres, sans mémorisation des résultats déjà calculés. Si n devient élevé le programme commence à ramer.
Version itérative — Le bon compromis pour un usage courant :
def fib_iter(n):
a = 0
b = 1
for _ in range(n):
a = b
b = a + b
return a
Une seule boucle, deux variables : c'est la version à connaître.
Version matricielle pour utiliser les bibliothèques du programme.
import numpy as np
import numpy.linalg as al
def fib_matrix(n):
M = np.array([[1, 1], [1, 0]])
V = np.array([[1],[0]])
return np.dot(al.matrix_power(M, n),V)al.matrix_power permet d'élever \(M\) à la puissance \(n\) sans repasser par la boucle terme à terme. C'est la traduction, en Python, de la méthode de diagonalisation. \(F_n\) est le deuxième coefficient de la matrice renvoyée.
Lire plus : Maîtriser l'informatique avec Prépa+
Conclusion
Que retenir de ce grand classique des concours ?
La suite de Fibonacci est définie par une suite récurrente linéaire d'ordre 2 : \(F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ pour } n \geq 2.\)
On peut facilement retrouver sa formule explicite (la formule de Binet) grâce à plusieurs méthodes. S'entraîner à utiliser la suite de Fibonacci avec d'autres outils du programme permet de vérifier sa compréhension, tout en se préparant à d'éventuels exercices de concours, écrits comme oraux.
Enfin, savoir coder la suite de Fibonacci en Python, de préférence la version itérative, est ce qui permet d'avoir des bases solides en informatique.
