Relations de Récurrence en Algorithmes

A- Récurrences linéaires homogènes à coefficients constants

Une formule de récurrence est dite linéaire homogène a coefficients constants si
elle est de la forme :

a0 tn + a1 tn−1 + . . . + ai tn−i + . . . + ak tn−k = 0.

Exemple 1 :

La suite de Fibonnacci se définit comme suit :

Celle-ci est une récurrence linéaire homogène a coefficients constants. Pour le voir,

Formule connue sous le nom de formule de de Moivre.

Exemple 2 :

Réécrivons la récurrence sous la forme :

tn − 5tn−1 + 8tn−2 − 4tn−3 = 0

Ses racines sont donc r1 = 1 de multiplicité m1 = 1 et r2 = 2 de multiplicité m2 = 2.
La solution générale est donc :

B- Récurrences linéaires non homogènes à coefficients constants

Considérons l'équation suivante :

Voici Une serie d'exercices PDF Relations de Récurrence Algorithmes et Complexité

Partie 1 : Relations de récurrence

Partie 2 : Algorithmes et complexité

Réucurrence

7 Kb