Équation qui définit chaque terme d'une suite ou d'un tableau discret en fonction de termes précédents et éventuellement de l'indice, accompagnée de condition(s) initiale(s) qui déterminent de manière unique la suite.

Principe

Spécifier un cas de base et une règle déterministe reliant termes ultérieurs et termes antérieurs de sorte que la suite entière se génère pas à pas ; les récurrences linéaires admettent des méthodes algébriques tandis que les non linéaires exigent d'autres techniques.

Démonstration

La récurrence de Fibonacci F_n = F_{n-1} + F_{n-2} avec F_0 = 0, F_1 = 1 génère la suite de Fibonacci ; sa linéarité permet une forme fermée via le polynôme caractéristique (formule de Binet).

Mauvaise application

Utiliser une récurrence sans fournir suffisamment de conditions initiales ou appliquer des techniques de résolution pour récurrences linéaires à des récurrences non linéaires, aboutissant à des suites ambiguës ou incorrectes.

Conséquence

Les récurrences fournissent des définitions constructives propices au calcul itératif, à l'analyse de complexité et aux estimations asymptotiques ; les récurrences linéaires se ramènent à des équations caractéristiques polynomiales et des génératrices.

Inversion

Une formule explicite en forme fermée pour le n‑ième terme qui n'exige pas les termes antérieurs pour l'évaluation et fournit un calcul direct et des asymptotiques analytiques.

Limite

Concerne des collections indexées discrètes (suites, tableaux) et exclut les équations différentielles continues, bien que des analogies avec les équations aux différences existent ; exige des données initiales/aux limites bien posées pour l'unicité.

Tension sémantique

Tension entre 'équation aux différences' utilisée largement (incluant relations avec décalages et inhomogénéités) et 'relation de récurrence' souvent réservée aux suites avec une règle génératrice avant fixe.

Synthèse

Une relation de récurrence est une règle plus données de base qui génère récursivement une suite discrète en exprimant chaque terme en fonction des précédents, permettant le calcul pas à pas et, pour les cas linéaires, une résolution algébrique et une analyse asymptotique.