Ex PGCD

Bonjour,
j'ai l'exercice de PGCD , aide moi svp
on a :
fonction PGCD(x, y entier) // x>y>=0;
if y=0 then return x ;
else return PGCD(y, x mod y);

Question:
Soit n(x,y) le nombre divisions ("mod")effectuees par l'algorithme
Montrer que n(x,y) = 0 si y =0
= 1+n(y, x mod y) sinon

montrer par récurrence que pour x>y>=0 , si n(x,y)=k alors x> F(k+2) (ou F(k+2) est le k+2 éme terme de la suite de Fibonacci
F(n) =0 si n=0
=1 si n=1
=F(n-1)+ F(n-2) si n>=2
et F(n) = 1\sqrt5 *(phi^n - phi'^n).

merci d'avance