Accueil

Lexique

Unités

ALGORITHMES

Tutoriel

Sommaire Algorithmes

Ici nous allons démontrer (pas complètement) comment arriver à la formule de Binet à partir de la suite de Fibonacci qui est une suite récurrente d'ordre 2, c'est à dire s'écrivant sous la forme:
U_n+1 = a.U_n+1 + b.U_n avec a = b = 1 dans le cas de la suite de Fibonacci.

Une suite géométrique V est défini comme étant:
V_n = k.qⁿ

On va chercher à savoir si on peut écrire la suite récurrente d'ordre 2 sous forme de suite géométrique récurrente d'ordre 2 de coefficient q (on admet qu'il est possible de réécrire la suite récurrente sous cette forme).

qn+2 = a.qn+1 + b.qn
qn+2 - a.qn+1 - b.qn = 0
qn.(q2 - a.q - b) = 0


Si q est un nombre complexe, (q² - a.q - b) = 0 a au moins une solution (double) ou 2 solutions.

Dans le cadre de la suite de Fibonacci, a = b = 1. On va donc chercher les solutions de (q² - q - 1) = 0.

Le discréminant s'écrit Δ = (-1)² - 4.(-1).1 = 5.

Δ est différent de 0 il y a donc 2 solutions :

• q₁ = (-(-1)-sqrt(5))/2 = (1-sqrt(5))/2
• q₂ = (1+sqrt(5))/2 : ceci est le négatif du Nombre d'Or

La solution générale (on l'admet) F_n = α.q₁ⁿ + β.q₂ⁿ

Et avec les conditions initiales de la suite de Fibonacci, à savoir F₀ = 0 et F₁ = 1, il vient le système:

1. F₀ = 0 = α.q₁⁰ + β.q₂⁰ = α + β
2. F₁ = 1 = α.q₁¹ + β.q₂¹ =α.q₁ + β.q₂

1. α = -β
2. α.q₁ - α.q₂ = 1

On résoud la ligne 2:

α.(q1 - q2) = 1
α= 1/(q1 - q2)
On remplace q1 et q2 par leurs valeurs et on calcule le dénominateur :
(1-sqrt(5))/2 - (1+sqrt(5))/2 = -2.sqrt(5)/2 = -sqrt(5)
donc, finalement, α= -1/sqrt(5) et β=1/sqrt(5)
Finalement:
Fn = ((-1-sqrt(5))/2)n/(-sqrt(5)) + ((-1+sqrt(5))/2)n/sqrt(5)
Soit
Fn = ((1+sqrt(5)/2)n/sqrt(5) - ((1-sqrt(5))/2)n/sqrt(5)


Sommaire Algorithmes