La matrice de Fibonacci

Application directe du cours · niveau 3 (difficile) · mathématiques (PCSI), chapitre 7 — Calcul matriciel et systèmes linéaires · B. Calculs de puissances

Énoncé

Soit $F = (1110)$ et $(F_{n})$ la suite de Fibonacci ( $F_{0} = 0$ , $F_{1} = 1$ , $F_{n + 2} = F_{n + 1} + F_{n}$ ). Montrer que pour tout $n \geq 1$ :

$F^{n} = (F_{n + 1} F_{n} F_{n} F_{n - 1}) .$

Corrigé

Par récurrence sur $n$ . Initialisation : $F^{1} = (1110) = (F_{2} F_{1} F_{1} F_{0})$ . ✔

Hérédité : si la formule vaut au rang $n$ ,

$F^{n + 1} = F \cdot F^{n} = (1110) (F_{n + 1} F_{n} F_{n} F_{n - 1}) = (F_{n + 1} + F_{n} F_{n + 1} F_{n} + F_{n - 1} F_{n}) = (F_{n + 2} F_{n + 1} F_{n + 1} F_{n}) .$

La récurrence de Fibonacci est encodée dans la multiplication matricielle : calculer $F^{n}$ par exponentiation rapide ( $F^{2 k} = (F^{k})^{2}$ ) donne $F_{n}$ en $O (lo g n)$ multiplications — c'est ainsi que les ordinateurs calculent les très grands nombres de Fibonacci.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.