La matrice de Fibonacci

Calcul matriciel et systèmes linéaires · B. Calculs de puissances · niveau 3 (difficile)

É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.

Énoncé

Corrigé

Exercices semblables