Une relation de récurrence est une équation qui utilise la récursivité pour relier des termes dans une séquence ou des éléments d’un tableau. C’est un moyen de définir une séquence ou un tableau en termes de lui-même. Les relations de récurrence ont des applications dans de nombreux domaines des mathématiques : théorie des nombres, combinatoire, distribution d’objets dans des bacs, calcul méthode d’Euler et beaucoup plus.
Les relations de récurrence sont utilisées lorsqu’une approche exhaustive de la résolution de problèmes est trop ardue pour être pratique. Bien qu’il ne soit pas idéal de calculer les termes dans une séquence, l’un après l’autre, en utilisant les termes précédents, cette approche peut être beaucoup plus efficace que la solution consistant à traiter les dossiers de manière exhaustive. Parfois, une relation de récurrence peut être « résolue » en définissant les termes d’une séquence en fonction de son index plutôt que des termes précédents dans la séquence. Cela donne une expression fermée pour chaque terme de la séquence et élimine la nécessité d’un processus itératif pour résoudre les termes de la séquence.
Comment définir une relation de récurrence ?
Une relation de récurrence est une équation qui définit une séquence basée sur une règle qui donne le terme suivant en fonction du terme précédent.
La forme la plus simple d’une relation de récurrence est le cas où le terme suivant ne dépend que du terme immédiatement précédent. Si nous désignons un terme de la séquence par xn, une telle relation de récurrence est de la forme :
xn + 1 = f (xn)
Pour une fonction f. Un tel exemple est xn + 1 = 2-xn / 2.
Une relation de récurrence peut également être d’ordre supérieur, où le terme xn + 1 pourrait dépendre non seulement du terme précédent xn, mais également de termes antérieurs tels que xn-1, xn-2, etc. Une relation de récurrence du second ordre dépend uniquement de xn et xn − 1 et est de la forme :
xn + 1 = f (xn, xn − 1)
Pour une fonction f avec deux entrées. Par exemple, la relation de récurrence xn + 1 = xn + xn-1 peut générer les nombres de Fibonacci.
Pour générer une séquence basée sur une relation de récurrence, il faut commencer par quelques valeurs initiales. Pour une récursion de premier ordre xn + 1 = f (xn), il suffit de commencer par une valeur initiale x0 et de générer tous les termes restants à l’aide de la relation de récurrence. Pour une récursion du second ordre xn + 1 = f (xn, xn − 1), il faut commencer par deux valeurs x0 et x1. Les relations de récurrence d’ordre supérieur nécessitent en conséquence davantage de valeurs initiales. Une relation de récurrence peut être considérée comme déterminante un système dynamique discret.
Quelles sont les différentes manières de résoudre les relations de récurrence ?
Il y a plusieurs façons de résoudre les relations de récurrence, on cite :
- Résoudre les relations de récurrence linéaires.
- Résoudre les relations de récurrence avec des fonctions génératrices.
- Résoudre les relations de récurrence avec la méthode de substitution.
- Résoudre les relations de récurrence avec la méthode des facteurs de sommation.
- Résoudre les relations de récurrence avec l‘algorithme informatique.