Suites et récurrences¶
Domaine : Algèbre · Niveau : débutant · Prérequis : aucun
L'idée¶
Une suite définie par récurrence donne chaque terme à partir des précédents. En olympiade, on ne demande presque jamais de calculer \(a_{2022}\) : on demande une propriété d'un terme lointain, ou de tous les termes. Deux outils font l'essentiel du travail.
- Le raisonnement par récurrence : si une propriété est vraie au départ et se transmet d'un terme au suivant, elle est vraie pour tous.
- L'étude de la suite : signe, monotonie, bornes, périodicité. Souvent après un changement de suite qui rend la relation plus simple.
La récurrence et ses variantes¶
- Récurrence simple. On montre \(P(n_0)\), puis que \(P(n)\) entraîne \(P(n+1)\).
- Récurrence forte. On montre que \(P(n_0), \ldots, P(n)\) ensemble entraînent \(P(n+1)\). Indispensable quand \(a_{n+1}\) dépend de plusieurs termes précédents.
- Renforcer l'hypothèse. Paradoxalement, un énoncé plus fort est parfois plus facile à prouver, car l'hypothèse de récurrence est elle aussi plus forte. Pour \(1 + \frac{1}{4} + \cdots + \frac{1}{n^2} < 2\), la récurrence directe échoue ; on prouve plutôt que la somme vaut au plus \(2 - \frac{1}{n}\), qui se transmet car \(\frac{1}{(n+1)^2} \leq \frac{1}{n} - \frac{1}{n+1}\).
Étudier une suite \(u_{n+1} = f(u_n)\)¶
- Points fixes. Les solutions de \(f(\ell) = \ell\) sont les seules limites possibles (si \(f\) est continue).
- Monotonie. Le signe de \(u_{n+1} - u_n = f(u_n) - u_n\) dépend de la position de \(u_n\) par rapport aux points fixes.
- Intervalle stable. Si \(f\) envoie un intervalle \(I\) dans lui-même et \(u_0 \in I\), tous les termes restent dans \(I\) (par récurrence).
- Cas arithmético-géométrique \(u_{n+1} = a u_n + b\) avec \(a \neq 1\) : avec le point fixe \(\ell = \frac{b}{1 - a}\), la suite \(u_n - \ell\) est géométrique de raison \(a\), donc \(u_n = \ell + a^n (u_0 - \ell)\).
Exemple résolu¶
Problème
On pose \(a_1 = 1\) et \(a_{n+1} = a_n + \dfrac{1}{a_n}\) pour \(n \geq 1\). Montrer que \(14 < a_{100} < 15\).
Étape 1 : changer de suite. La relation est plus simple pour les carrés :
Tous les termes sont strictement positifs (récurrence immédiate), donc \(a_{n+1}^2 > a_n^2 + 2\).
Étape 2 : minorer par récurrence. De \(a_1^2 = 1\) et \(a_{n+1}^2 \geq a_n^2 + 2\), on tire \(a_n^2 \geq 2n - 1\) pour tout \(n \geq 1\). En particulier \(a_{100}^2 \geq 199 > 196 = 14^2\), donc \(a_{100} > 14\).
Étape 3 : majorer en réinjectant la minoration. En sommant la relation de l'étape 1 de \(n = 1\) à \(99\) (un télescopage) :
Le terme \(k = 1\) vaut \(1\). Pour \(k \geq 2\), l'étape 2 donne \(\frac{1}{a_k^2} \leq \frac{1}{2k - 1}\) : les quatre termes \(k = 2, \ldots, 5\) valent au plus \(\frac{1}{3}\) et les \(94\) termes \(k = 6, \ldots, 99\) au plus \(\frac{1}{11}\). Donc
Conclusion. \(14 < a_{100} < 15\).
Le passage à \(a_n^2\) a transformé une relation non linéaire en une relation presque arithmétique (\(+2\) à chaque pas, plus une petite erreur). C'est le même mécanisme que dans 2021 A7.
Comment le reconnaître¶
- La suite est définie par une relation entre termes consécutifs, et l'énoncé porte sur un terme lointain (\(a_{2017}\), \(a_{2022}\)) ou sur tous les termes.
- L'énoncé dit « pour tout \(n\) » et chaque cas se déduit du précédent.
- La relation est une inégalité entre trois termes consécutifs : on cherche une propriété qui se propage plutôt qu'une formule.
- Une suite finie avec des conditions qui « bouclent » (\(a_{n+1} = a_1\)) : on la prolonge en suite périodique.
Techniques classiques¶
| Situation | Technique |
|---|---|
| La récurrence directe ne passe pas | Renforcer l'énoncé à prouver |
| Relation non linéaire | Changer de suite : carrés (exemple résolu), inverses, quotients \(\frac{u_{n+1}}{u_n}\), différences \(u_{n+1} - u_n\), ou une combinaison comme \(y_i = 2x_i + x_{i+1}\) |
| \(u_{n+1} = f(u_n)\) | Points fixes, signe de \(f(x) - x\), intervalle stable |
| \(u_{n+1} = a u_n + b\) | Soustraire le point fixe pour obtenir une suite géométrique |
| \(u_{n+2} = p u_{n+1} + q u_n\) | Équation caractéristique (section suivante) |
| Inégalité entre termes consécutifs | La sommer : les termes intermédiaires se télescopent |
| Conditions cycliques sur une suite finie | Prolonger en suite périodique ; une suite périodique n'est jamais strictement croissante |
Exercices d'échauffement¶
- On pose \(u_0 = 0\) et \(u_{n+1} = 2u_n + 1\). Montrer que \(u_n = 2^n - 1\).
- On pose \(u_0 = 5\) et \(u_{n+1} = 3u_n - 2\). Exprimer \(u_n\) en fonction de \(n\). Indication : point fixe.
- On pose \(a_1 = 1\) et \(a_{n+1} = \frac{a_n}{1 + a_n}\). Calculer \(a_n\). Indication : étudier \(\frac{1}{a_n}\).
- Montrer que \(1 + \frac{1}{4} + \frac{1}{9} + \cdots + \frac{1}{n^2} < 2\) pour tout \(n \geq 1\), en renforçant l'énoncé.
- On pose \(u_0 = 0\) et \(u_{n+1} = \sqrt{2 + u_n}\). Montrer que la suite est croissante et majorée par \(2\).
Suites dans la shortlist¶
- 2015 A1 : récurrence sur \(n\), avec deux cas selon que \(a_{n+1} \geq 1\) ou \(a_{n+1} < 1\).
- 2021 A7, solution 1 : avec \(y_i = 2x_i + x_{i+1}\), on obtient \(y_i^2 \geq y_{i-1}^2 + 6\), d'où \(y_i \geq \sqrt{6i}\) par récurrence.
- 2018 A2 : on prolonge la suite en une suite infinie périodique, qui ne peut pas être strictement croissante.
- 2022 A1 : une inégalité entre trois termes consécutifs, exploitée par comparaison de signes plutôt que par un calcul explicite.
- 2018 A4 : une récurrence sur l'écart entre le plus grand et le plus petit des termes possibles.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 2 (M. Aassila), p. 10 (raisonnement par récurrence), p. 13 (récurrence de Cauchy), p. 31 (récurrence et suites), p. 87 à 111 (suites arithmétiques, géométriques, majorées, périodiques), p. 116 (suites \(u_{n+1} = f(u_n)\)), p. 128 (suites et inégalités).
Pour aller plus loin : la suite de Fibonacci et les suites périodiques¶
Récurrences linéaires d'ordre 2¶
Une suite vérifie une récurrence linéaire d'ordre 2 si \(u_{n+2} = p\,u_{n+1} + q\,u_n\) pour tout \(n\), avec \(p, q\) fixés. On lui associe l'équation caractéristique
Si cette équation a deux racines distinctes \(r_1\) et \(r_2\), il existe des constantes \(A\) et \(B\) telles que
On trouve \(A\) et \(B\) avec les deux premiers termes.
La suite de Fibonacci¶
Elle est définie par \(F_0 = 0\), \(F_1 = 1\) et \(F_{n+2} = F_{n+1} + F_n\) :
L'équation caractéristique \(r^2 = r + 1\) a pour racines \(\varphi = \frac{1 + \sqrt{5}}{2}\) et \(\psi = \frac{1 - \sqrt{5}}{2}\). On obtient la formule de Binet :
Comme \(|\psi| < 1\), \(F_n\) est l'entier le plus proche de \(\varphi^n / \sqrt{5}\) : la suite croît comme une suite géométrique de raison \(\varphi \approx 1{,}618\).
Trois propriétés à connaître :
- Identité de Cassini : \(F_{n+1} F_{n-1} - F_n^2 = (-1)^n\) pour tout \(n \geq 1\).
- Théorème de Zeckendorf : tout entier \(N \geq 1\) s'écrit de façon unique comme somme de nombres de Fibonacci d'indices au moins \(2\), non consécutifs. Par exemple \(100 = 89 + 8 + 3\).
- Comptage : le nombre de façons de paver une bande \(1 \times n\) avec des carrés \(1 \times 1\) et des dominos \(1 \times 2\) est \(F_{n+1}\). Le dernier morceau est un carré ou un domino, d'où la relation \(a_n = a_{n-1} + a_{n-2}\).
Quand y penser. Dans un problème de comptage, on regarde les premiers cas. Si l'on trouve \(1, 2, 3, 5, 8\), on cherche une relation \(a_n = a_{n-1} + a_{n-2}\) en distinguant ce que fait le dernier élément.
Suites périodiques¶
Si une suite vérifie \(u_{n+1} = f(u_n)\) et ne prend qu'un nombre fini de valeurs, elle est périodique à partir d'un certain rang. En effet, par le principe des tiroirs, deux termes \(u_i = u_j\) avec \(i < j\) sont égaux. Ensuite, la suite répète les mêmes termes avec la période \(j - i\).
Par exemple, la suite des restes de Fibonacci modulo \(m\) est périodique, et même périodique dès le début. On applique le même argument aux couples \((F_n, F_{n+1})\) modulo \(m\), qui ne prennent que \(m^2\) valeurs. De plus, on peut parcourir la suite à l'envers grâce à \(F_n = F_{n+2} - F_{n+1}\), donc la répétition remonte jusqu'au premier terme.
Dans la shortlist¶
- 2020 C1 : le nombre de permutations vérifie \(P_n = P_{n-1} + P_{n-2}\), et la réponse est \(F_{n+1}\).
- 2018 C1, remarque : une construction générale avec les nombres de Fibonacci.
- 2017 N6, remarque 1 : les solutions construites sont \(x_n = F_{2n+1} + 1\).
- 2020 C4 : l'énoncé porte directement sur les nombres de Fibonacci.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 2 (M. Aassila), p. 116 à 118 (récurrences linéaires) et p. 122 (Fibonacci, Cassini, Zeckendorf).
Problèmes de la shortlist¶
40 problèmes · difficulté moyenne : ★★★★★ (3,0) · dont 5 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 5 · 2 ★ : 10 · 3 ★ : 10 · 4 ★ : 11 · 5 ★ : 4
| Problème | Difficulté | Concepts |
|---|---|---|
| 2022 A1 | ★☆☆☆☆ | - |
| 2018 A2 · OIM P2 | ★☆☆☆☆ | Sommes, télescopage et transformation d'Abel |
| 2015 A1 | ★☆☆☆☆ | Sommes, télescopage et transformation d'Abel · AM-GM et moyennes |
| 2014 A1 · OIM P1 | ★☆☆☆☆ | Principe extrémal |
| 2013 A1 | ★☆☆☆☆ | Bijections et dénombrement · Polynômes : racines, relations de Viète, factorisation |
| 2023 N4 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2017 C3 | ★★☆☆☆ | Récurrence et constructions récursives · Invariants et monovariants · Bijections et dénombrement |
| 2017 A4 | ★★☆☆☆ | Principe extrémal |
| 2015 N4 | ★★☆☆☆ | Invariants et monovariants · Divisibilité, PGCD et algorithme d'Euclide |
| 2014 A2 | ★★☆☆☆ | Invariants et monovariants |
| 2011 A2 | ★★☆☆☆ | Polynômes : racines, relations de Viète, factorisation |
| 2010 A4 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2007 A1 · OIM P1 | ★★☆☆☆ | Principe extrémal |
| 2006 A1 | ★★☆☆☆ | Partie entière et majorations |
| 2006 A2 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2024 A5 | ★★★☆☆ | Sommes, télescopage et transformation d'Abel · AM-GM et moyennes · Principe extrémal |
| 2023 N5 | ★★★☆☆ | Principe extrémal · Divisibilité, PGCD et algorithme d'Euclide |
| 2018 A4 | ★★★☆☆ | - |
| 2018 A5 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2013 C5 | ★★★☆☆ | Principe des tiroirs |
| 2009 C3 | ★★★☆☆ | Récurrence et constructions récursives |
| 2009 A5 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2009 A6 · OIM P3 | ★★★☆☆ | Sommes, télescopage et transformation d'Abel · Principe extrémal |
| 2008 A4 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2006 A3 | ★★★☆☆ | Principe extrémal |
| 2025 A6 | ★★★★☆ | Principe des tiroirs · Divisibilité, PGCD et algorithme d'Euclide |
| 2023 N6 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2021 A7 | ★★★★☆ | Sommes, télescopage et transformation d'Abel · AM-GM et moyennes · Convexité, inégalité de Jensen, lissage |
| 2021 N7 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal |
| 2017 A7 | ★★★★☆ | Principe extrémal |
| 2014 N7 | ★★★★☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE |
| 2012 A6 | ★★★★☆ | Principe extrémal · Principe des tiroirs |
| 2010 N6 | ★★★★☆ | Valuations p-adiques et lemme LTE · Graphes : degrés, chemins, arbres |
| 2010 A7 · OIM P6 | ★★★★☆ | Principe des tiroirs · Principe extrémal |
| 2009 N6 | ★★★★☆ | Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler |
| 2007 A5 | ★★★★☆ | Cauchy-Schwarz et lemme de Titu |
| 2024 A8 | ★★★★★ | Principe extrémal · Divisibilité, PGCD et algorithme d'Euclide |
| 2022 A8 | ★★★★★ | Principe des tiroirs · Bijections et dénombrement |
| 2014 A6 | ★★★★★ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Équations diophantiennes : factorisation et encadrement |
| 2009 N7 | ★★★★★ | Résidus quadratiques · Valuations p-adiques et lemme LTE |