précédent | suivant | table des matières

Complexité : Récurrence

Définitions.

Une suite récurrente de nombres est définie par une relation de récurrence et un ensemble de conditions initiales.

Résoudre une équation de récurrence signifie chercher le terme général d’une suite récurrente.

Dans une relation de récurrence, le terme T_n est fonction d’un certain nombre de termes pour des entiers compris entre un certain n₀ et n-1.

T_n = f ( { T(p), n0≤p<n} )

• Si n₀ = n-k, on dit que la relation de récurrence est d’ordre k. Ainsi :
  • Si T_n ne dépend que de T_n-1, on parle d’ordre 1.
  • Si T_n dépend de T_n-1 et T_n-2 (ou que de T_n-2) on parle d’ordre 2.
• Si tous les termes T_p, p<n interviennent dans T_n, on parle de relation de récurrence complète.
• Quand f est une combinaison linéaire des T_p, on parle de relations de récurrence linéaire.

Relation de récurrence non linéaire

Une équation de récurrence non linéaire mais simple peut être ramenée à une relation linéaire par passage au logarithme.

Par exemple, à l’ordre 1, T_n = a_n × ( T_n ) ^p devient : 
      S_n = log ( T_n )
      S_n = log ( a_n × ( T_n-1 ) ^p )
      S_n = log (a_n ) + p×log ( T_n-1 )
      S_n = log ( a_n ) + p×S_n-1

Il ne reste plus qu’à résoudre une équation linéaire puis à opérer le changement de domaine inverse.

Relation de récurrence complète

L’idée pour résoudre une équation de récurrence complète est de réduire l’ordre.

T_n = a + b_n + c×T₀+ ... + c×T_n-1

Une telle relation peut être ramenée à une relation linéaire en effectuant la différence des termes T_n-T_n-1.
T_n-T_n-1 = b_n - b_n-1 + c×T_n-1
T_n = b_n - b_n-1 + (c+1)×T_n-1

Résolution des récurrences par les fonctions génératrices

Pour n∈N, soit (a_n ) une suite de nombres réels et (f_n(x)) une suite de fonctions numériques réelles. On appelle fonction génératrice ou (série génératrice) de (associée à, représentant) la suite (a_n) la série formelle A(x) = Σ_n≤0 a_n×f_n(x) Les fonctions f_n(x) constituent le noyau de la fonction génératrice ou (série génératrice).

On n'étudiera que les cas où le noyau est de la forme  f_n(x)=xⁿ ou f_n(x)=xⁿ/n!. Dans le premier cas on parlera de fonction génératrice ordinaire ou (série génératrice ordinaire) et dans le deuxième cas on parlera de fonction génératrice exponentielle ou (série génératrice exponentielle).

Pour résoudre une récurrence décrivant une suite (a_n), on utilisera la technique suivante : 

• Multiplier les deux membres de la relation de récurrence par x_n, ou x_n/n! et sommer sur n
• Evaluer les sommes pour en tirer une équation vérifiée par la sgo , (sge)
• Résoudre cette équation pour obtenir une formule explicite de la fgo , (fge).
• Développer la fgo (fge) en série entière pour obtenir les coefficients (les termes de la suite d’origine).

Voir les fonctions génératrices ordinaires et les fonction génératrices exponentielles.

haut de la page