récurrences

Les récurrences, ou récurrences, désignent des relations qui définissent une suite à partir de ses termes précédents. Elles expriment a_n en fonction des a_{n-1}, a_{n-2}, etc., et éventuellement d’une fonction n. On parle de récurrence linéaire lorsque a_n est une combinaison linéaire des termes antérieurs, avec des coefficients constants.

Une récurrence linéaire d’ordre k et homogène a la forme a_n = c1 a_{n-1} + ... + ck a_{n-k} pour n ≥ k, avec des conditions initiales a_0, ..., a_{k-1} données. Si un terme indépendant f(n) apparaît, on parle de récurrence non homogène. Des exemples typiques incluent la suite de Fibonacci, définie par a_n = a_{n-1} + a_{n-2} avec a_0 = 0 et a_1 = 1, et les suites géométriques où a_n = r a_{n-1}.

Méthodes de résolution: pour les récurrences linéaires à coefficients constants, on obtient une solution générale via l’équation caractéristique x^k − c1 x^{k−1} − ... − ck = 0. Les racines déterminent la forme des solutions (linéaires, exponentielles, ou combinées). D’autres approches existent, comme les générateurs, les méthodes matricielles ou les solutions approchées lorsque pas de forme fermée n’est disponible.

Applications: les récurrences interviennent largement en informatique (programmation dynamique, analyse d’algorithmes), en combinatoire pour dénombrer des objets, et dans les modèles de processus discrets.

Limites: certaines récurrences non linéaires ou non constantes échappent à une résolution explicite, et leur étude porte aussi sur le comportement asymptotique et les conditions initiales.