MATHEMATICAL.

[Link]
MATHEMATIK-OLYMPIADE
OLYMPIADES DE MATHÉMATIQUES
OLIMPIADI DELLA MATEMATICA

Les suites

Arnaud Maret
Actualisé: 1er août 2021
vers. 1.2.1

Table des matières

1 Introduction 2
1.1 Un premier exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Un deuxième exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Un peu de théorie 5
2.1 Le jargon et quelques résultats de base . . . . . . . . . . . . . . . . . . . 6
2.2 Suites arithmétiques et géométriques . . . . . . . . . . . . . . . . . . . . 9
3 Conclusion 11
3.1 Trucs et astuces à l'emporter . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Un dernier exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Méthodes supplémentaires 14
4.1 Récursion explicite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1 Introduction
Depuis quelques années, les problèmes d'algèbre aux Olympiades Internationales se ré-
orientent au-delà des classiques équations fonctionnelles et autres inégalités en trois va-
riables. Ces nouveaux problèmes s'articulent désormais autour de suites de nombres. Leur
solution est faite de manipulations algébriques et d'outils plus standards tels que l'induc-
tion. Souvent astucieuse et courte, la solution se décline parfois à l'aide de méthodes plus
académiques, voire algorithmiques. Certains de ses problèmes ont une saveur de théorie
des nombres, voire de combinatoire.
Ce script fournit une brève introduction au sujet, couvrant les dénitions des concepts
de base, ainsi que les principaux résultats élémentaires. Une place de choix est laissée
aux exemples. Il y a en eet, tout comme pour les équations fonctionnelles, très peu de
théorie. Il va s'en dire que la pratique est la clé pour maitriser les problèmes de suites.
La plupart des exemples et des exercices sont empruntés du recueil de problèmes d'algèbre
101 Problems in Algebra from the training of the USA IMO Team par T. Andrescu et Z.
Feng1 .

1.1 Un premier exemple

Exemple 1 (IMO 2014) Soit a0 , a1 , . . . une suite de nombres entiers strictement positifs
telle que a0 < a1 < . . .. Montrer qu'il existe un unique nombre entier n ≥ 1 tel que
a0 + a1 + . . . + an
an < ≤ an+1 .
n
Première solution. Soit a1 , a2 , . . . une suite qui satisfait les hypothèses du problème. On
nous demande de montrer l'existence et l'unicité d'un certain nombre. Nous rédigerons
donc la solution au propre en mettant en évidence ces deux parties distinctes.
Tout d'abord, commençons par l'étape zéro de tout problème de suites. C'est-à -dire,
on va, dans un premier temps, oublier la donnée du problème et se concentrer uni-
quement sur l'expression algébrique fournie. C'est une phase d'observation et de
tâtonnement. On va manipuler l'expression donnée de multiples manières avec pour but
d'obtenir des formulations équivalentes mettant certaines propriétés, a priori dissimulée,
en évidence.
1 disponible en ligne sous [Link]
[Link]

2
Par exemple, ici, en regroupant les termes en an à gauche, on obtient
 
a0 + . . . + an 1 a0 + . . . + an−1
an < ⇐⇒ 1− an <
n n n
a0 + . . . + an−1
⇐⇒ an < . (1)
n−1
En utilisant l'hypothèse an > an−1 dans (1), il s'en suit
a0 + . . . + an a0 + . . . + an−1
an < =⇒ an−1 < . (2)
n n−1
La relation (2) met en évidence un comportement inductif. Comme dans toute argu-
mentation par induction proprement rédigée, on introduit des variables logiques indexées
sur n. Soient
1. L(n): l'inégalité an < a0 +...+an
n
est vériée,
2. R(n): l'inégalité a0 +...+an
n
≤ an+1 est vériée.
On peut reformuler le problème en termes des variables logiques L(n) et R(n): il s'agit
de montrer qu'il existe un unique entier n tel que L(n) et R(n) sont vraies.
La relation (1) peut être reformulée par L(n) ⇔ R(n − 1), où la notation barrée indique
la négation de la proposition (c'est-à -dire, R(n) est vraie si an+1 < (a0 + . . . + an )/n).
La relation (2), quant à elle, peut être écrite L(n) ⇒ L(n − 1). En combinant ces deux
relations abstraites à l'aide de la transitivité de l'implication, il s'en suit que R(n) ⇒ L(n)
et R(n − 1) ⇒ R(n). En résumé, les relations suivantes sont vériées:
(i) L(n) ⇔ R(n − 1),
(ii) L(n) ⇒ L(n − 1),
(iii) R(n − 1) ⇒ R(n),
(iv) R(n) ⇒ L(n).
Si l'on considère les petits cas, alors on remarque que L(1) est toujours vraie parce que
a0 > 0 par hypothèse. Par contre, nous ne pouvons rien déduire de la valeur logique de
R(1) en général.
Il existe donc deux cas de gure possibles. Soit L(n) est vraie pour tout n ou il existe un
indice k ≥ 2 minimal tel que L(k) soit fausse. On va synthétiser ces deux cas à l'aide de
tableaux.
1. Supposons que L(n) soit vraie pour tout n. Par (i), on obtient que, si L(n) est vraie
pour tout n, alors R(n) est fausse pour tout n:
n 1 2 3
L(n) ...
R(n) × × × ...

3
 2. Dans le deuxième cas, on suppose qu'il existe un indice k ≥ 2 minimal tel que L(k)
soit fausse. Ainsi, par minimalité, L(n) est vraie pour tout n < k. La relation (ii)
implique que L(n) est fausse pour tout n ≥ k. En utilisant la relation (i), on obtient
n k−2 k−1 k k+1 k+2
L(n) ... × × × ...
R(n) ... × ...
Revenons au problème posé. On doit montré l'existence et l'unicité d'un indice n tel que
L(n) et R(n) soient simultanément vraies. Dans notre table, c'est le cas si exactement
une colonne contient deux . On observe que c'est le cas dans le deuxième tableau. Il
ne reste plus qu'à exclure le cas où L(n) est vraie pour tout n.
Si L(n) est vraie pour tout n, alors pour tout n on a
(n − 1)an − an−1 − . . . − a1 < a0
⇐⇒ (an − an−1 ) + (an − an−2 ) + . . . + (an − a1 ) < a0 .

Rappelez-vous que an − an−1 > 0. Or, comme an − an−1 est un nombre entier par hy-
pothèse, on a en fait an − an−1 ≥ 1. C'est une estimation classique et c'est aussi le seul
endroit où l'on emploie l'hypothèse que la suite a0 , a1 , . . . est une suite de nombres entiers.
De même, an − ai ≥ 1 pour i < n. Donc, on obtient
n − 1 < a0 , ∀n ≥ 1.

Contradiction.

Deuxième solution. Que signie montrer l'existence dans ce problème ? On a une col-
lection d'intervalles (an , an+1 ] et une collection d'expressions (a0 + . . . + an )/n. Il faut
montrer qu'une de ces expressions se trouve dans le bon intervalle. Il serait plus simple
si l'expression que l'on cherchait à localiser ne dépendait plus de n. Autrement dit, s'il
on avait une seule expression donnée et une collection d'intervalles, quitte à modier les
intervalles que l'on considère.
On peut arriver à cette n en isolant a0 , par exemple:
a0 + a1 + . . . + an
an < ≤ an+1
n
⇐⇒ (n − 1)an − an−1 − . . . − a1 < a0 ≤ nan+1 − an − . . . − a1 .

Avec bn := (n − 1) · an − an−1 − . . . − a1 , on obtient

a0 + a1 + . . . + an
an < ≤ an+1 ⇐⇒ bn < a0 ≤ bn+1 .
n
Observer que b1 = 0 et bn+1 − bn = n(an+1 − an ) > 0. L'existence du n recherché est donc
équivalente à l'existence d'un intervalle (bn , bn+1 ] contenant a0 .

4
 | | | | R
b1 = 0 b2 b3 b4

Si la suite b1 , b2 , . . . de nombres entiers n'est pas bornée par en-dessus, alors les intervalles
(bn , bn+1 ] partitionnent la demi-droite réelle de zéro (= b1 ) à plus l'inni. On écrit
+∞
[
(0, +∞) = (bi , bi+1 ].
i=1

Ainsi, a0 étant un nombre strictement positif, il se trouve nécessairement dans l'un de ces
intervalles. Cela conclut la preuve de l'existence. Or, comme les intervalles sont disjoints,
cela montre également l'unicité.
Il se pourrait que la suite b1 , b2 , . . . soit bornée par en-dessus par un entier strictement
inférieur à a0 , au quel cas l'existence désirée ne serait pas vériée. Or, dans ce cas, on
pourrait écrire
bn = (n − 1)an − an−1 − . . . − a0
= (an − an−1 ) + (an − an−2 ) + . . . + (an − a1 ).

L'argument de la première solution implique que bn ≥ n − 1 et la suite b1 , b2 , . . . n'est

donc pas bornée.

1.2 Un deuxième exemple

Exemple 2 maybe ?

2 Un peu de théorie
Dénition 2.1 Une suite est une collection ordonnée, en général innie ou semi-innie,
de nombres. Par exemple de nombres naturels, entiers ou réels. On notera (xn )n≥a pour
une suite (semi-innie) indexée à partir de a ∈ Z et (xn )∞
n=−∞ pour une suite (innie)
indexée sur Z.

Remarque Observer qu'une suite de nombres (xn )n≥1 n'est rien d'autre qu'une fonction
f : N → R, Z, N, . . . vers l'ensemble approprié. De même, une suite (xn )∞
n=−∞ n'est rien
d'autre qu'une fonction des nombres entiers Z.
La remarque précédente signie qu'un problème de suites peut être reformulé comme un
problème d'équations fonctionnelles où les fonctions qui nous intéressent sont dénies sur
les nombres entiers. Malgré ces similarités au niveau de la formulation et des objets étu-
diés, ces deux catégories de problèmes, suites et équations fonctionnelles, sont diérentes
en nature. Un problème de suite insiste en général sur le comportement inductif des
indices (xn xn+k ), alors qu'une équation fonctionnelle met en évidence les itérations
d'une fonctions (en incluant des termes du type f (f (x))).

5
2.1 Le jargon et quelques résultats de base

Nous commençons par dénir quelques termes de base du jargon des suites.

Dénition 2.2 Une suite (xn ) est:

ˆ (strictement) croissante si
(>)
xn+1 ≥ xn , ∀n.

ˆ (strictement) décroissante si
(<)
xn+1 ≤ xn , ∀n.

ˆ constante s'il existe un nombre c tel que

xn = c, ∀n.

On note xn ≡ c.
ˆ périodique si il existe un nombre entier k ≥ 1 tel que

xn+k = xn , ∀n.

Le plus petit tel k est appelé la période de (xn ).

Exemple 3 Les suites suivantes sont périodiques.

1. Les suites constantes sont périodiques de période 1.
2. La suite xn := (−1)n est périodique de période 2.
3. La suite xn := sin( 2πn
m
) est périodique de période m.
Une propriété pratique est la suivante. La preuve est laissée en exercice.

Lemme 2.1 Une suite (dé)croissante qui est périodique est nécessairement constante.
Dénition 2.3 Une suite (xn ) est bornée par en-dessous s'il existe un nombre réel A tel
que
A ≤ xn , ∀n
et bornée par en-dessus s'il existe un nombre réel B tel que
xn ≤ B, ∀n.

Elle est bornée si elle est bornée à la fois par en-dessus et par en-dessous. Les nombres
A et B sont appelés des bornes (les bornes ne sont évidemment pas uniques).

6
Par exemple, une suite de nombres (strictement) positifs est par dénition bornée par en-
dessous. Pour aller plus loin dans cette idée, on peut dénir bornée de manière équivalente
en exigeant l'existence d'un nombre réel M tel que |xn | ≤ M, ∀n. En eet, par dénition
de la valeur absolue,
|xn | ≤ M ⇐⇒ −M ≤ xn ≤ M.

La propriété d'être bornée est reliée aux propriétés de (dé)croissance par le lemme suivant.

Lemme 2.2 Une suite bornée par en-dessus/en-dessous et croissante/décroissante converge.

On ne va volontairement pas rentrer dans les détails techniques de la dénition de conver-
gence dans ce script. La notion intuitive de convergence est susante pour les problèmes
olympiques. Par exemple, les suites constantes sont convergentes. La suite xn := 1/n
converge vers 0. La suite xn := n2 diverge vers plus l'inni. La suite xn := (−1)n n'est
pas convergente.
Intuitivement, une suite croissante, représentée dans un système d'axes, ne peut que
"monter". Si elle est bornée par en-dessus, alors il existe un plafond qu'elle n'est pas
autorisée à dépasser. Ne pouvant pas redescendre, la suite va "converger" vers une valeur
en-dessous du plafond.

Exemple 4 Soit (xn )n≥1 une suite de nombres réels telle que x1 = 2 et
xn 1
xn+1 = + , ∀n ≥ 1.
2 xn
Trouver une expression explicite pour xn .

Solution. On commence par calculer les premiers de termes de la suite. Cela permettra
de mettre évidence certaines propriétés de la suite. On calcule
x1 = 2, x2 = 3/2 = 1.5, x3 = 17/12 ∼ 1.42, . . .

On remarque que la suite parait rester positive, malgré une certaine décroissance. Mon-
trons tout d'abord que la suite (xn ) est une suite de nombres strictement positifs. En
eet, par induction, x1 > 0 et xn+1 > 0 si xn > 0.
En allant un peu plus loin, on remarque que
√
xn ≥ 2, ∀n ≥ 1.
√
En eet, par induction, x1 = 2 > 2 et en utilisant AM-GM, comme xn > 0, on obtient
√
r
xn 1 xn 1
xn+1 = + ≥2· · = 2.
2 xn 2 xn

7
Que peut-on dire de l'éventuelle (dé)croissance de la √
suite ? Une petite inspection montre
que la suite est décroissante. En eet, comme xn ≥ 2,
xn 1 xn xn
xn+1 = + ≤ + = xn .
2 xn 2 2

La suite (xn ) étant décroissante et bornée par en-dessous, elle est donc convergente.
Comment déterminer la valeur vers laquelle la suite converge ? L'astuce est la suivant: à
la limite, lorsque l'indice n est très grand, on a "xn+1 = xn " parce que la suite converge.
Si on dénote par x la limite de la suite (xn ), alors, en supposant xn+1 = xn = x, on a
x 1 √
x= + ⇐⇒ x = ± 2.
2 x
√ √
Comme xn ≥ 2, on a x = 2.
Pour simplier la notation, parce
√ que l'on préfère travailler avec suites qui convergent
vers zéro, on pose yn := xn − 2. La condition initiale devient
√
yn+1 = xn+1 − 2
xn 1 √
= + − 2
2 x
√n
yn + 2 1 √
= + √ − 2
2 yn + 2
2
yn
= √ .
2(yn + 2)
√
L'astuce algébrique intervient à présent. On reconnait en le terme 2(yn + 2) un semblant
de√double produit qui pourrait s'associer au terme yn2 . Il manque cependant un facteur
2 2. En l'ajoutant, on obtient
√
√ yn2 √ (yn + 2 2)2
yn+1 + 2 2 = √ +2 2= √ .
2(yn + 2) 2(yn + 2)

En contemplant les deux dernières expressions, on remarque un schéma inductif. Plus

précisément,
√ 2
yn2

yn+1 2(yn + 2) yn
√ = √ · √ = √ .
yn+1 + 2 2 2(yn + 2) (yn + 2 2)2 yn + 2 2
C'est gagné! Une telle formule
√ inductive est trop esthétique pour ne pas être la clé du
problème. Comme y1 = 2 − 2, on peut écrire
 2  2n−1 √ !2n−1
yn+1 yn y1 2− 2
√ = √ = ... = √ = √ .
yn+1 + 2 2 yn + 2 2 y1 + 2 2 2+ 2

8
En revenant à la suite (xn ), on obtient
√ √ !2n−1
xn+1 − 2 2− 2
√ = √
xn+1 + 2 2+ 2

qui nous permet d'isoler xn+1 et de conclure.

2.2 Suites arithmétiques et géométriques

Deux grandes familles de suites sont présentées dans les exemples suivants.

Exemple 5 (Suites arithmétiques) Une suite (xn ) (innie ou semi-innie) est arithmé-
tique s'il existe un nombre r, appelé raison, tel que xn+1 = xn +r pour tout n. En français,
chaque élément de la suite est obtenu à partir du précédent en ajoutant r. Montrer que
si (xn ) est une suite arithmétique de raison r, alors

xn = x0 + nr, ∀n.

Solution. Nous raisonnons évidemment par induction. Si n = 0, le résultat est clair.

Supposons à présent que le résultat est vérié pour n et montrons le pour n + 1. Par
dénition et en utilisant l'hypothèse d'induction,
xn+1 = xn + r = (x0 + nr) + r = x0 + (n + 1)r.

Si la suite est indexée sur Z, alors, de même, on peut montrer que si la conclusion est
vériée pour n, alors elle l'est aussi pour n − 1.

Selon la valeur de la raison, une suite arithmétique satisfait les propriétés suivantes:
ˆ si r = 0, alors la suite est constante.
ˆ si r 6= 0, alors la suite diverge vers l'inni. Plus précisément, si r > 0, alors la suite
diverge vers plus l'inni, et si r < 0, alors la suite diverge vers moins l'inni.

Exemple 6 (Suites géométriques) Une suite (xn )n≥0 est géométrique s'il existe un
nombre r, appelé raison, tel que xn+1 = r · xn pour tout n ≥ 0. En français, chaque
élément de la suite est obtenu à partir du précédent en multipliant par r. Montrer que si
(xn )n≥0 est une suite arithmétique de raison r, alors

xn = r n · x0 , ∀n ≥ 0.

La solution est inductive tout comme pour les suites arithmétiques.

Si x0 = 0, alors la suite (xn )n≥0 est constamment nulle. Selon la valeur de la raison, une
suite géométrique satisfait les propriétés suivantes. Ici, on suppose que x0 6= 0.

9
 ˆ si r = 0, alors la suite est constamment nulle (excepté x0 qu'on a supposé non-nul):
xn ≡ 0.
ˆ si r = 1, alors la suite est constante.
ˆ si r > 1 et x0 6= 0, alors la suite est divergente vers plus ou moins l'inni selon le
signe de x0 .
ˆ si 0 < |r| < 1, alors la suite est convergente vers zéro.

Exemple 7 Soit (xn )n≥1 une suite de nombres réels non-nuls telle que
xn−2 xn−1
xn = , ∀n ≥ 3.
2xn−2 − xn−1

Trouver toutes les valeurs possibles de x1 et x2 telles que la suite (xn ) prenne une valeur
entière pour une innité d'indices n.

Première solution. Soit (xn ) une telle suite. On commence par l'étape des manipulations
algébriques. En manipulant l'expression donnée de diverses manières, on obtient tôt ou
tard la relation suivante:
xn−2 xn−1 1
xn = = 2 1 .
2xn−2 − xn−1 xn−1
− xn−2

Cette relation met en évidence le rôle joué par l'inverse des xn . En eet, on a
1 2 1
= − .
xn xn−1 xn−2

Cette expression suggère immédiatement la substitution yn := 1/xn qui est valable parce
que les xn sont tous non-nuls. La nouvelle suite (yn ) satisfait la relation clé suivante:
yn + yn−2 = 2yn−1 .

Cette relation implique que la suite (yn ) est une suite arithmétique (cf exercice). On a
ainsi deux cas de gure possibles selon la valeur de la raison r de la suite (yn ). Si r 6= 0,
alors la suite (yn ) est divergente vers plus ou moins l'inni. Si r = 0, la suite est constante.
En utilisant que la suite (xn ) est entière pour une innité d'indices n, on sait que |xn | ≥ 1
pour cette même innité d'indices n (car xn 6= 0 par hypothèse). Pour ces mêmes indices
n, on a |yn | ≤ 1. Donc, la suite (yn ) ne diverge pas vers l'inni. Elle est donc constante
par la remarque précédente.
La suite (xn ) est également constante et cette constante est un nombre entier non-nul.
Par conséquent, x1 = x2 est un nombre entier non-nul.
Inversement, si x1 = x2 est un nombre entier non-nul, alors xn = x1 pour tout n et la
suite (xn ) prend donc bien des valeurs entières pour une innité d'indices n.

10
Deuxième solution. Soit à nouveau (xn ) une suite qui satisfait les conclusions du pro-
blème. Dans cette solution, on commence plutôt par calculer les premiers termes de la
suite. On obtient xx 1 2
x3 = ,
2x1 − x2
puis
x2 x3 x2 2xx11−x
x2
2
x 1 x2
x4 = = x1 x2 = .
2x2 − x3 2x2 − 2x1 −x2 3x1 − 2x2
On est dès lors tenté de conjecturer que
x1 x 2 x1 x2
xn = = .
(n − 1)x1 − (n − 2)x2 n(x1 − x2 ) + 2x2 − x1

Une simple induction permet de vérier cette armation.

La présence du n au dénominateur de l'expression explicite pour xn montre que (xn )
converge vers zéro à part si x1 = x2 , au quel cas le n du dénominateur ne joue aucun
rôle. Comme la suite (xn ) est par hypothèse jamais nulle, elle ne peut prendre qu'un
nombre ni de fois une valeur entière si elle converge vers zéro. On en déduit donc que
la suite (xn ) ne converge pas vers zéro et donc x1 = x2 . La n de la preuve est identique
à la solution précédente.

3 Conclusion
3.1 Trucs et astuces à l'emporter

L'approche suivante est un modèle à adopter pour attaquer un problème de suite.

a.1) Manipulations algébriques: Comme dans les exemples précédents, il est bon
de commencer par jouer avec l'expression donnée dans le problème, en oubliant le
reste de l'énoncé. Manipuler l'expression à foison en essayant de faire apparaitre
des motifs inductifs, télescopiques ou toute formule esthétique.
Cette étape est clé et le temps à lui consacrer ne doit pas être négligé. En général, les
problèmes ont plusieurs solutions dont une courte et subtile, et une plus technique
et plus longue, mais moins astucieuse.
a.2) Propriétés standards: On s'intéresse également, dans la phase d'approche, aux
éventuelles propriétés satisfaites par la suite donnée dans le problème (par exemple
périodicité, (dé)croissance,. . . ).
Il est également utile, lorsque qu'une formule inductive est donnée, de calculer
explicitement les premiers termes d'une suite. Dans certains cas, on peut même
espérer obtenir une formule explicite à partir d'une formule inductive.
b) Mettre de l'ordre: En utilisant les observations faites aux points précédents, on
peut tenter de simplier l'expression algébrique à l'aide de substitutions pertinentes

11
 (par exemple yn := 1/xn , ∆n := xn − xn−1 ou yn := xn − x où x est la limite
conjecturée de la suite (xn )). Une bonne substitution vous permettra d'y voir plus
clair.
c) Se concentrer sur la conclusion: C'est l'étape ou l'on retourne au problème
initial et on essaie de mettre bouts à bouts les éléments obtenus précédemment
pour démontrer l'énoncé voulu.
Allez! Encore un dernier exemple pour la route.

3.2 Un dernier exemple

Exemple 8 (OFM 2020, Problem 3) Let (xn )n≥1 be sequence of real numbers such that
x1 = 3/2 and
n
xn+1 = 1 + , ∀n ≥ 1.
xn
Find an integer k ≥ 1 such that 2020 ≤ xk < 2021.

Solution. First thing to do is computing some values of the sequence. They may exhibit
(or disprove) some properties of the sequence. Here we compute
x1 = 3/2 = 1.5, x2 = 5/3 ∼ 1.67, x3 = 11/5 = 2.2, x4 = 26/11 ∼ 2.36, . . .

One can guess at this point is that the sequence (xn ) is increasing. However, it does not
seem so obvious to prove (for instance by trying a good old induction). Why ? Well, the
right-hand side of the initial condition is decreasing in the variable xn . So, nding a lower
bound for the right-hand side is equivalent to nding an upper bound for xn . Thus in
order to conclude that xn+1 > xn one should rst bound xn from above. Some kind of
double induction may work. But let's try something else for now.
Looking at the assertion we have to prove, it seems that the sequence (xn ) (conjecturally
increasing) is not convergent. More precisely, this suggests to study its asymptotic
behaviour: how fast do is it grow ? If you think of the index n of the sequence (xn ) as
a count of minutes and xn as the state after n minutes, then the problem asks for the
time at which the sequence will be between two given "large" values.
The standard trick to approximate the asymptotic behaviour of (xn ), given the recursive
condition in the problem statement, is to let "xn+1 = xn " and see what comes out. Be
careful! This is a purely heuristic argument and has no value as part of a proof). It simply
let you make an educated guess of the asymptotic value. So let x := xn+1 = xn > 0, we
get √
n 1 + 1 + 4n p
x=1+ ⇒ x= = 1/2 + 1/4 + n.
x 2
Note that the case x = 1/2 − 1/4 + n wasp excluded because x > 0. The conclusion is
p

that we expect
p (xn ) to behave like 1/2 + 1/4 + n when n goes to innity. We write
xn ∼ 1/2 + 1/4 + n.

12
Now you have to realize that the term 1/4 under the square root has a very little inuence
on the behaviour at innity. Indeed, if n → ∞, then the 1/4 has almost no weight
compared to n. More precisely, it is true that
p √
lim 1/4 + n − n = 0.
n→∞
√
So, we expect xn ∼ 1/2 + n when n goes to innity.
√
We could also get rid of the 1/2 in the sense that n goes to innity as n goes to innity,
so the contribution of the 1/2 is negligible. However, we have to locate some xk in an
interval of length 2021 − 2020 = 1 and 1/2 is not negligible compared to 1. So, it is
important to keep in mind that the 1/2 may √ actually have some importance here. But
for simplicity, let's rst assume that xn ∼ n. If this leads nowhere, then we will try
with the 1/2 (and if this is still not enough, then we might try with the 1/4 as well).
√
What now? If we expect xn ∼ n when n is large, we could try to use the square root in
this estimation to bound xn from above and below. Looking at the rst terms computed
above, it seems that the inequality
√ √
n ≤ xn ≤ 1 + n

holds. Let's try to prove it. By induction, we assume it is true for xn . For xn+1 , we have
n √ √
xn+1 = 1 + ≤ 1 + n < 1 + n + 1,
xn
and n n
xn+1 = 1 + ≥1+ √ .
xn n+1
So, we would like to prove that
n √ √ √ √
1+ √ ≥ n+1 ⇐⇒ n+1+ n ≥ ( n + 1) n + 1.
n+1
A cool manoeuvre at this point consists in observing that the above inequality is equi-
valent to √ √ 2
( n + 1) − n+1 ≥ 0.

So we proved that √ √
n ≤ xn ≤ 1 + n, ∀n ≥ 1,
and actually that √ √
n ≤ xn < 1 + n, ∀n ≥ 1.
So in particular k = 20202 satises the desired conclusion.

We were lucky with our approach. We guessed the asymptotic behaviour of the sequence
and then got rid of some low-contribution terms in order to simplify the computations
later on. This was nothing more than a bold bet, maybe motivated by some gut feeling.

13
The moral here is that you have to try stu instead of simply being stuck somewhere.
Keep writing, keep trying, always! If you realize your assumption were not sharp
enough, then try with something sharper. And trust your feeling (a.k.a. experience ), it
is always your best friend when sitting an exam.

4 Méthodes supplémentaires
4.1 Récursion explicite

Disclaimer: l'auteur original de ces notes reste à ce jour inconnu.

Dans certains cas spéciques, il existe des méthodes pour trouver une formule explicite
pour une suite dénie récursivement. Soit (xn )n≥1 une suites de nombres réels où les k
valeurs x1 , . . . , xk sont supposées connues et qui est dénie par l'équation de récurrence
xn+k + ck−1 xn+k−1 + . . . + c1 xn+1 + c0 xn = 0, ∀n ≥ 1. (3)
Les ci sont ici des constantes. La suite (xn )n≥1 est uniquement déterminée par les infor-
mations ci-dessus. Cela signie que si l'on trouve une expression pour xn qui satisfait la
relation ci-dessus, alors il s'agit de la suite recherchée. Pour ce genre suite, dénie par
une relation de récurrence linéaire en les variables xn , il existe une méthode pour trouver
une formule explicite pour la suite (xn )n≥1 .
On introduit tout d'abord, de manière purement formelle, le polynôme caractéristique
P (λ) de la suite (xn )n≥1 en remplaçant les termes xn par λn dans la relation (3). On
obtient
P (λ) := λk + ck−1 λk−1 + . . . + c1 λ + c0 = 0.
Remarquer qu'on a simplié par λn . L'idée est la suivant. Si l'on connait les zéros du
polynômes caractéristiques, i.e. les nombres λ pour lesquels P (λ) = 0, alors on peut
construire une suite (xn )n≥1 qui satisfait la relation désirée.
Soient λ1 , . . . , λr les zéros (complexes) distincts de P (λ) avec leurs multiplicités respec-
tives m1 , . . . , mr ≥ 1. Noter que m1 + . . . + mr = n. Pour 1 ≤ i ≤ r et 0 ≤ j ≤ mi − 1,
on introduit la solution fondamentale
Fi,j (n) := nj · λni .

La suite (xn )n≥1 est une combinaison linéaire des solutions fondamentales. En eet

Théorème 4.1 Il existe des constantes (complexes) Ci,j tels que

r m
X X i −1

xn = Ci,j · Fi,j (n), ∀n ≥ 0.

i=1 j=0

Les coecients Ci,j sont uniquement déterminées par les valeurs x1 , . . . , xk qu'on a sup-
posées connues. Ces valeurs fournissent un système linéaire de k équations en k variables

14
Ci,j . Ce que l'on peut résoudre. En pratique, la valeur de k n'est jamais trop élevée, ce
qui permet de résoudre le système sans trop de problème.

Exemple 9 La suite de Fibonacci est dénie par F0 = 0, F1 = 1 et par la formule de

récurrence Fn+2 = Fn+1 + Fn pour n ≥ 0. Trouver une formule explicite pour (Fn )n≥0 .

Solution. Le polynôme caractéristique de la suite

√ de Fibonacci est P (λ) = λ − λ − 1.
2

Les deux zéros du polynôme sont λ1,2 = (1 ± 5)/2 et ils sont√les deux de mulltiplicité
√
1. Les deux solutions fondamentales sont par conséquent ((1 + 5)/2)n et ((1 − 5)/2)n .
Nous obtenons ainsi une formule de la forme
√ !n √ !n
1+ 5 1− 5
Fn = C1 + C2 .
2 2
Les constantes C1 , C2 peuvent être déterminées à l'aide des valeurs F0 = 0 et F1 = 1. Le
système d'équations suivant doit être satisfait:
0 = C1 + C2 ,
√ ! √ !
1+ 5 1− 5
1 = C1 + C2 .
2 2
√ √
Il s'ensuit que C1 = 1/ 5 et C2 = −1/ 5, ce qui nous amène à la formule de Binet bien
connue: √ !n √ !n !
1 1+ 5 1− 5
Fn = √ − .
5 2 2

Exemple 10 La suite de Lucas ressemble à celle de Fibonacci. Elle est dénie par
L1 = 1, L2 = 3 et la formule de récurrence Ln+2 = Ln+1 + Ln pour n ≥ 1. Trouver une
formule explicite pour la suite (Ln )n≥1 .

Solution. Pour simplier les calculs, il est utile de poser L0 := 2. Cela est consistant par
rapport à l'équation de récurrence. La suite de Lucas et celle de Fibonacci ont la même
équation de récurrence et par conséquent les mêmes solutions fondamentales. Il n'y a que
les constantes qui changent. Le nouveau système d'équations est
2 = C1 + C2 ,
√ ! √ !
1+ 5 1− 5
1 = C1 + C2 .
2 2
Les solutions sont C1 = C2 = 1, ce qui entraîne
√ !n √ !n
1+ 5 1− 5
Ln = + .
2 2

15
Remarque (Fun fact of the day) On peut obtenir beaucoup de résultats spectaculaires à
partir des expressions explicites que l'on vient de trouver. Un exemple plutôt anodin est
la formule de limite bien connue pour la suite de Fibonacci
√
Fn 1+ 5
lim = .
n→∞ Fn−1 2
Le terme de droite s'appelle le nombre d'or. Il apparaît de façon très naturelle dans les
problèmes d'emplacement optimal. Cela explique peut-être pourquoi la suite de Fibonacci
est aussi omniprésente dans la nature (comptez par exemple le nombre de spirales d'une
pomme de pin ou les spirales dans une eur de tournesol).
Dans l'exemple suivant, le polynôme caractéristique possède des zéros multiples:

Exemple 11 Deux suites (an )n≥0 et (bn )n≥0 satisfont les équations suivantes:
bn = an + an−1 + an−2 ,
bn + bn−2 = 3(an−1 + an−3 ),

ainsi que a0 = a1 = 1 et b2 = b3 = 4. Trouver une formule explicite pour (an )n≥0 .

Solution. En introduisant la première équation dans la deuxième, nous obtenons

an − 2an−1 + 2an−2 − 2an−3 + an−4 = 0, ∀n ≥ 4.

Le polynôme caractéristique P (λ) = λ4 − 2λ3 + 2λ2 − 2λ + 1 = (λ2 + 1)(λ − 1)2 admet le

zéro double λ = 1 et les deux zéros complexes conjugués λ = ±i. D'après la proposition
1, il existe des constantes C1 , C2 , C3 , C4 telles que
an = C1 + C2 · n + C3 · in + C4 · (−i)n .

En partant des valeurs initiales données et de la première équation en haut, nous obtenons
facilement a2 = 2 et a3 = 1. Cela nous donne le système d'équations
1 = C1 + C3 + C4
1 = C1 + C2 + iC3 − iC4
2 = C1 + 2C2 − C3 − C4
1 = C1 + 3C2 − iC3 + iC4

avec les solutions C1 = 2, C2 = −1/2, C3 = (−2+i)/4 et C4 = (−2−i)/4. En remplaçant

ces valeurs dans la formule ci-dessus, on obtient
(mod 4)

 1 − n/2 n≡0
(mod 4)

3/2 − n/2 n≡1

an =
 3 − n/2 n≡2 (mod 4)
(mod 4).

5/2 − n/2 n≡3


16
Cet exemple met en lumière le fait que même si la suite (an )n≥0 est clairement réelle, il se
peut qu'il y ait des nombres complexes dans la formule explicite. Toutefois si l'équation
de récurrence n'a que des coecient réels, alors les zéros complexes du polynôme caracté-
ristique apparaissent toujours accompagnés de leurs conjugués, ce qui est par conséquent
le cas pour les termes complexes de la formule explicite également. Si les valeurs initiales
sont réelles, alors les coecients correspondants sont également conjugués et en eectuant
les transformations adéquates on arrive à faire disparaître les parties imaginaires de la
formule. Il ne reste que des nombres réels. Ceci peut être démontré, mais pour vous il
sut de le savoir. Dans la plupart des applications il devient vite clair comment certains
termes se simplient.
Voici maintenant une véritable application. On peut utiliser la méthode qu'on vient de
développer pour résoudre une équation fonctionnelle en une variable qui ne contient que
des itérations pures de la fonction f .

Exemple 12 Trouver toutes les fonctions f : R>0 → R>0 telles que pour tout x > 0
f (f (x)) + f (x) = 2x.

Solution. Soit f une solution de l'équation. Soit a > 0 un nombre arbitraire. Dénis-
sons une suite (xn )n≥0 par x0 := a et xn+1 := f (xn ). Nous avons alors, par hypothèse,
l'équation de récurrence
xn+2 + xn+1 = 2xn .
Le polynôme caractéristique P (λ) = λ2 + λ − 2 admet les zéros 1 et −2. Il existe donc
des constantes C1 et C2 avec
xn = C1 · 1n + C2 · (−2)n .

Comme f ne prend que des valeurs positives, tous les termes xn de la suite doivent être
positifs. Si on avait C2 6= 0, alors il y aurait des n très grands pour lesquels le côté droit
de la formule serait négative, contradiction. Par conséquent C2 = 0 et xn = C1 pour tout
n. Commex0 = a, on obtient f (a) = a. Comme a était arbitraire, on a montré que f était
la fonction identité.

Une représentation explicite peut donc souvent être utile. L'opération inverse est ce-
pendant tout aussi importante. Il y a souvent des termes qui font penser à certaines
formules explicites de suites dénies récursivement. A l'aide de l'équation de récurrence,
nous pouvons parfois démontrer des assertions concernant la divisibilité et autres sujets
semblables. En voici maintenant un exemple.
√
Exemple 13 Existe-t-il un nombre naturel impair n tel que b(2 + 5)n c soit divisible
par 99?

17
Solution. L'expression donnée sous cette forme ne convient pas du tout à des considé-
rations de divisibilité. Pour des raisons de symétrie, on pourrait considérer à la place
l'expression √ √
an := (2 + 5)n + (2 − 5)n . (4)
√
Nous allons montrer que an est toujours un nombre entier. Comme 0 > 2 − 5 > −1, il
s'ensuivra directement que pour un n impair, nous avons
√ n √ √
b(2 + 5) c = (2 + 5)n + (2 − 5)n .

L'expression (4) fait penser à la formule explicite d'une suite dénie récursivement. Nous
allons maintenant reconstruire cette
√ formule de récurrence. Le polynôme caractéristique
doit admettre les deux zéros 2 ± 5, nous avons donc
√ √
P (λ) = (λ − 2 − 5)(λ − 2 + 5) = λ2 − 4λ − 1.

La formule de récurrence est par conséquent

an+2 = 4an+1 + an .

Nous avons de plus a0 = 2 et a1 = 4. Par conséquent, an est entier pour tout n ≥ 0.

Nous devons encore décider si il existe un entier n tel que an peut être divisible par 99.
Pour cela nous allons considérer la suite (an )n≥0 modulo 9 et modulo 11. Un calcul rapide
nous donne les périodes minimales
an ≡ 2, 4, 0, 4, 7, 5, 0, 5 (mod 9), an ≡ 2, 4, 7, 10, 3, 0, 3, 1, 7, 7 (mod 11).

Il s'ensuit que
9 | an ⇔ n ≡ 2, 6 (mod 8) and 11 | an ⇔ n ≡ 5 (mod 10).

Ces deux congruences ne sont jamais satisfaites en même temps, par conséquent an n'est
jamais divisible par 99.

18