Bonjour,

Je suis en licence de maths et j'ai vraiment du mal à démarrer cette exo. J'ai fais l'initialisation j'ai réussi (avec un peu bcp d'aide) a montrer dans la 1er récurrence que

(Complexité de l'algorithme d'Euclide)

On rappelle que l'algorithme d'Euclide peut être présenté par la fonction euclide(. , .)

euclide(a,b) =

a          
si  b=0,
                            
euclide(b,r)
si b != 0,  et où a=bq+r avec 0 <= r < b.

On appelle n'ombres d'étapes dans l'exécution de l'algorithme le nombre d'appel récursifs de la fonction euclide(a,0) s'effectue en 0 étapes
On définit la suite de Fibonacci (Fn)n>=0 par la relation de récurrence suivante:

F(0) = 0 , F(1)=1
Pour tout entiers naturel n supérieur ou égale à 0,
F(n+2) = F(n) + F(n+1)


1.  ✨Montrer par récurrence sur k>= 0 que si: a et b sont deux entiers positifs avec a>0 et a>=b et si euclide(a,b) s'effectue en k étapes alors a>= F(k+1) et b>=F(k)

2. ✨En déduire que pour tout entier k>=1 et pour tous entier a, b >= 0 avec a>=b, si b<F(k) alors(a,b) s'effectue au plus en k étapes

3. ✨Montrer par récurrence sur k que euclide F(k+1)* F(k) s'effectue en exactement k étapes.



4. ✨On note “…”
(Désolé je fuis latex)
(appelé nombre d'or).
En admettant les deux résultats suivants:

(a)lim n tend vers +infini de (F(n+1)/F(n) = nombre d'or)

(b) Fn est environ égale au (nombre d'or)**n divise par racine de 5

montrer que le nombre d'étapes pour effectuer euclide (a,b) est O(log b)c'est-à-dire qu'il existe une constante C>=O telle que, si N(a.b) désigne le nombre d'étapes dans l'évaluation de la fonction
euclidel4.0). 00 a
N(a, b) ≤ Clogb

Merciii infiniment vous me sauverez j'en ai marre d'enchaîner les corrections sans comprendre la matière que je fais. Vous me serez d'une grande aide ❤️