Aller au contenu

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.

  1. 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.
  2. 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 :

\[a_{n+1}^2 = a_n^2 + 2 + \frac{1}{a_n^2}.\]

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) :

\[a_{100}^2 = 1 + 2 \cdot 99 + \sum_{k=1}^{99} \frac{1}{a_k^2}.\]

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

\[a_{100}^2 \leq 199 + 1 + \frac{4}{3} + \frac{94}{11} < 199 + 11 = 210 < 225 = 15^2.\]

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

  1. On pose \(u_0 = 0\) et \(u_{n+1} = 2u_n + 1\). Montrer que \(u_n = 2^n - 1\).
  2. On pose \(u_0 = 5\) et \(u_{n+1} = 3u_n - 2\). Exprimer \(u_n\) en fonction de \(n\). Indication : point fixe.
  3. On pose \(a_1 = 1\) et \(a_{n+1} = \frac{a_n}{1 + a_n}\). Calculer \(a_n\). Indication : étudier \(\frac{1}{a_n}\).
  4. 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é.
  5. On pose \(u_0 = 0\) et \(u_{n+1} = \sqrt{2 + u_n}\). Montrer que la suite est croissante et majorée par \(2\).

Parcours suggéré

Un choix de problèmes de la shortlist, du plus accessible au plus difficile, où ce concept joue le premier rôle. La liste complète est plus bas.

Étape 1 — Premiers pas (1 ★)

  • 2014 A1 ★☆☆☆☆ · OIM P1 : Pour une suite strictement croissante d'entiers, un unique \(n\) place la moyenne \((z_0 + \cdots + z_n)/n\) entre \(z_n\) et \(z_{n+1}\).
  • 2018 A2 ★☆☆☆☆ · OIM P2 : Pour quels \(n\) existe-t-il une suite circulaire de \(n\) réels vérifiant \(a_i a_{i+1} + 1 = a_{i+2}\) ?
  • 2022 A1 ★☆☆☆☆ : Une suite positive vérifiant \(a_{n+1}^2 + a_n a_{n+2} \leq a_n + a_{n+2}\) a son \(2022\)-ième terme au plus \(1\).

Étape 2 — Consolidation (2 ★)

  • 2011 A2 ★★☆☆☆ : Trouver les suites de \(2011\) entiers telles que \(x_1^n + 2x_2^n + \cdots + 2011 x_{2011}^n\) soit toujours de la forme \(a^{n+1} + 1\).
  • 2014 A2 ★★☆☆☆ : Deux points de départ itérés par la même fonction définie par morceaux : à une étape, l'un monte pendant que l'autre descend.
  • 2017 A4 ★★☆☆☆ : Une suite définie par \(a_n = -\max_{i+j=n}(a_i + a_j)\) au-delà d'un certain rang est bornée.

Étape 3 — Approfondissement (3 ★)

  • 2018 A4 ★★★☆☆ : Chaque terme est la moyenne de quelques termes précédents, choisis librement : quelle est la plus grande valeur de \(a_{2018} - a_{2017}\) ?
  • 2023 N5 ★★★☆☆ : Une suite croissante dont chaque terme divise le double de la somme des précédents : si elle fait intervenir une infinité de premiers, tout entier divise l'un de ses termes.

Étape 4 — Défi (4 ★ – 5 ★)

  • 2017 A7 ★★★★☆ : Une récurrence dont le signe dépend de \(b_{n-1}\) : l'un des termes \(a_{2017}\), \(a_{2018}\) vaut au moins \(2017\).
  • 2009 N7 ★★★★★ : Pour deux entiers distincts \(a, b > 1\), le produit \((a^n - 1)(b^n - 1)\) n'est pas toujours un carré parfait.

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

\[r^2 = p\,r + q.\]

Si cette équation a deux racines distinctes \(r_1\) et \(r_2\), il existe des constantes \(A\) et \(B\) telles que

\[u_n = A\,r_1^n + B\,r_2^n \quad \text{pour tout } n.\]

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\) :

\[0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ \ldots\]

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 :

\[F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}.\]

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 ★★☆☆☆ -
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