Récurrence

Vuiiii

21 Décembre

Je vous avais fait un petit topo y a quelques jours sur comment gérer des égalités de
sommes par récurrence. On va maintenant consolider tout ça.

L’idée de base de la récurrence c’est d’imaginer une suite de dominos : si un tombe,

les autres suivront.

Ainsi pour démontrer des propriétés mathématiques, on peut suivre la même approche
et essayer de montrer que si une propriété est vraie pour un entier n1 alors elle est vraie
pour un autre entier n2 qui lui-même entraine un entier n3 dans sa chute et ainsi de
suite. Si on arrive à obtenir tous les entiers de la sorte, on a démontré notre propriété.

Bon c’était absolument pas clair et c’est tout à fait normal, dans la plupart des
récurrences on va en fait simplement montrer que n entraine n + 1 dans sa chute et
ça suffira.

En l’occurence, l’hérédité consistera à essayer de se ramener à quelque chose qui se

rapproche le plus possible de ce qu’on avait au rang n pour avoir utiliser notre hypothèse
de récurrence. En d’autres termes, l’objectif ça va souvent être de faire du forcing pour
faire apparaitre l’expression du rang n dans celle du rang n + 1.

J’ai beaucoup parlé (pas tant en fait) mais je pense qu’une série d’exemples sera plus
convainquante. Je me contenterai de l’hérédité :).

n+1
n a −1
Example 1 Montrer par récurrence sur n que si a ≠ 1 on a 1 + a + ⋅ ⋅ ⋅ + a = a−1
.
n+1
n a −1
On suppose donc avoir 1 + a + ⋅ ⋅ ⋅ + a = a−1
et on veut montrer que :
n+2
n+1 a −1
1 + a + ⋅⋅⋅ + a = .
a−1
n+1
L’objectif c’est de transformer 1 + a + ⋅ ⋅ ⋅ + a en un truc qui ressemble davantage à
n
1 + a + ⋅ ⋅ ⋅ + a . Par exemple on peut dire que :
n+1 n
1 + a + ⋅⋅⋅ + a = a(1 + a + ⋅ ⋅ ⋅ + a ) + 1,

1
et dans ce cas on a fini puisque :
n+1 n
1 + a + ⋅⋅⋅ + a = a(1 + a + ⋅ ⋅ ⋅ + a ) + 1
n+2
−a a
= +1
a−1
n+2
a −a+a−1
=
a−1
n+2
a −1
= .
a−1
Bon c’était ptet pas très parlant mais on a pu voir le principe : ici on a cherché à ex-
primer le truc du rang n + 1 en fonction du truc du rang n pour créer un lien entre les
deux qui nous permette d’utiliser l’hypothèse de récurrence.

n
Example 2 Montrer par récurrence sur n que pour x ∈ [−1, +∞[ on a (x+1) ≥ 1+nx.
n n+1
Ok donc supposons avoir (x + 1) ≥ 1 + nx et montrons que (x + 1) ≥ 1 + (n + 1)x.
On peut écrire que :
n+1 n
(x + 1) = (x + 1) × (x + 1),
donc finalement puisque x + 1 ≥ 0 :
n+1 n
(x + 1) = (x + 1) × (x + 1)
≥ (1 + nx)(x + 1)
2
= x + x n + 1 + xn
2
= 1 + (n + 1)x + x n
≥ 1 + (n + 1)x.
n
Donc on est bon. Cette fois ci l’astuce c’était de faire apparaitre (x + 1) pour ensuite
utiliser l’inégalité qu’on avait et conclure naturellement.

n 2
Example 3 Montrer par récurrence que si n ≥ 4 on a 2 ≥ n .
n+1 n
On a naturellement 2 = 2 × 2 donc on peut lier le rang n + 1 au rang n ! On écrit
ainsi :
n+1 n
2 =2×2
2
≥ 2n .
2 2
On voudrait ainsi montrer que pour n ≥ 4 on a 2n ≥ (n + 1) . Bon ça se résume à
2 2
n ≥ 2n + 1, ce qui est clairement vrai. Par exemple puisque n ≥ 4 on a n ≥ 4n ≥
2n + n > 2n + 1.

Ici une fois encore on a fait apparaitre le rang n dans le rang n + 1 pour utiliser
l’hypothèse de récurrence.

2
Example 4 Montrer par récurrence sur n que :
n
n+1
∏(2k + 1)! ≥ ((n + 1)!) .
k=0

n
n+1
Encore une fois on va supposer avoir ∏(2k + 1)! ≥ ((n + 1)) et on va bidouiller pour
k=0
n+1
n+2
montrer que ∏(2k + 1)! ≥ ((n + 2)) .
k=0
n+1 n
On peut écrire que ∏(2k + 1)! = (2(n + 1) + 1)! ∏(2k + 1)! : on a trouvé notre lien
k=0 k=0
entre le rang n et le rang n + 1. Ainsi :
n+1 n
∏(2k + 1)! = (2n + 3)! ∏(2k + 1)!
k=0 k=0
n+1
≥ (2n + 3)! ((n + 1)!) .
n+2
Bon du coup on aimerait bien que ce truc là soit plus grand que ((n + 2)!) . On veut
ainsi montrer que :
n+1 n+2
(2n + 3)! ((n + 1)!) ≥ ((n + 2)!) .
En l’occurence ici on se doute qu’on peut beaucoup simplifier : on a plein de produits
de nombres petits.

Ainsi puisque (n + 2)! = (n + 2)(n + 1)! on peut écrire :

n+2 n+2 n+2
(n + 2)! = (n + 2) (n + 1)! ,

donc il s’agit de montrer que :

n+2
(2n + 3)! ≥ (n + 2) (n + 1)!.

Mais là c’est clair puisque (2n + 3)! ça va être le produit des entiers entre 1 et n + 1 fois
n+2
le produit des entiers entre n + 2 et 2n + 3. Or (n + 2)(n + 3) . . . (2n + 3) ≥ (n + 2)
puisque c’est le produit de n + 2 termes plus grand que n + 2 ! Et hop là c’est finito.

Bon ici la mentalité c’est que pour que notre récurrence se fasse le plus simplement
possible, on veut montrer une inégalité, et il se trouve qu’on peut beaucoup simplifier et
qu’après simplification on obtient quelque chose qui se voit.

Un dernier exemple pour la route.

∗ 1
Example 5 a. Soit x ∈ R+ , montrer que x + x
≥ 2.

3
 b. Montrer par récurrence que pour tous réels x1 , x2 , . . . , xn strictement positifs :

1 1 1 2
(x1 + x2 + ⋅ ⋅ ⋅ + xn ) ( x + x + ⋅ ⋅ ⋅ + x ) ≥ n .
1 2 n

√ 2
Pour la partie a on remarque que ça revient à dire que ( x − √1x ) ≥ 0, ce qui est vrai.
On ne sait pas encore à quoi ça va servir, mais on le garde dans un coin de notre tête
pour la partie b.

Ok donc une fois encore on suppose avoir :

1 1 1 2
(x1 + x2 + ⋅ ⋅ ⋅ + xn ) ( x + x + ⋅ ⋅ ⋅ + x ) ≥ n ,
1 2 n

et on veut montrer que :

1 1 1 1 2
(x1 + x2 + ⋅ ⋅ ⋅ + xn + xn+1 ) ( x + x + ⋅ ⋅ ⋅ + x + x ) ≥ (n + 1) .
1 2 n n+1

Pour ça on veut faire apparaitre

1 1 1
(x1 + x2 + ⋅ ⋅ ⋅ + xn ) ( x + x + ⋅ ⋅ ⋅ + x )
1 2 n

dans
1 1 1 1
(x1 + x2 + ⋅ ⋅ ⋅ + xn + xn+1 ) ( x + x + ⋅ ⋅ ⋅ + x + x )
1 2 n n+1

pour pouvoir utiliser notre hypothèse de récurrence. On va donc écrire que :

n n
1 1 1 1 1
(x1 + ⋅ ⋅ ⋅ + xn + xn+1 ) ( x + ⋅ ⋅ ⋅ + x + x ) = (∑ xi + xn+1 ) (∑ x + x )
1 n n+1 i n+1
i=1 i=1
n n n n
1 1 1
= ∑ xi ∑ x + xn+1 ∑ x + x ∑ xi + 1
i i n+1
i=1 i=1 i=1 i=1
n n
2 1 1
≥ n + 1 + xn+1 ∑ x + x ∑ xi .
i n+1
i=1 i=1

n n
1 1
Ok donc finalement il nous reste à minorer xn+1 ∑ x + x ∑ xi .
i n+1
i=1 i=1
Là on voit pas trop quelle tête ça a donc revenons aux trois petits points :
xn+1 xn+1 x1 x2
x1 + x2 + ⋅ ⋅ ⋅ + xn+1 + xn+1 + . . .
1 xn+1 x1
Ah mais là se souvient que x + x
≥ 2 donc en fait x1
+ xn+1
≥2!

4
 Ainsi on voit bien que notre somme va être plus grand que 2n : on va faire n groupes
de 2 termes dont la somme est plus grande que 2. Autrement dit on va écrire :
n n n n
1 1 xn+1 xi
xn+1 ∑ x + x ∑ xi = ∑ x + ∑ x
i n+1 i n+1
i=1 i=1 i=1 i=1
n
xn+1 xi
=∑ x +x
i n+1
i=1
n
≥ ∑2
i=1
= 2n.

Donc finalement :
1 1 1 2 2
(x1 + ⋅ ⋅ ⋅ + xn + xn+1 ) ( x + ⋅ ⋅ ⋅ + x + x ) ≥ n + 2n + 1 = (n + 1) ,
1 n n+1

et on a fini.

Ici une fois encore on force pour faire apparaitre ce qu’on a au rang n dans le rang
n + 1 afin d’utiliser notre hypothèse de récurrence. Une fois cela fait on essaye d’aller au
plus simple, et ça marche.

Ok alors parfois on est en présence de plusieurs paramètres et on peut donc légitimement

se demander sur lequel faire sa récurrence. Dans ce cas on regarde pour chacun à quel
point ça modifie beaucoup l’expression, et donc à quel point ça semble simple de se
ramener à un truc qui ressemble le plus possible au rang n. Bon comme d’hab c’était
pas clair, faisons un exemple.

n
(j) j ∗
Example 6 On définit Sn = ∑ k . Montrer par récurrence que pour n, p ∈ N on a :
k=1

p−1
(p) p+1 p + 1 (k)
(p + 1)Sn = (n + 1) −1−∑( )Sn .
k
k=0

Bon quand on voit ça on se dit visiblement que celui qui nous a donné l’exo nous veut
beaucoup de mal : y a trop de notations on s’embrouille. Aie aie aie.

Ok on essaye de rester zen et de pas fixer trop longtemps cette formule moche. A la
place on va déjà se demander sur qui faire notre récurrence. Pour ça on regarde comment
ça bouge si on fait varier p et n.

- Si on tente avec p alors passer de p à p + 1 ça change les coefficients binomiaux et

les exposants, ça a l’air un peu compliqué à gérer donc on regarde si ça serait pas mieux

5
de tenter avec n.

- Si on tente avec n alors passer de n à n + 1 ça va pas changer les coefficients binomi-
k (k)
aux et ça va juste faire apparaitre des (n + 1) dans les Sn qui vont sortir de la somme
p
et être gentils. En plus le ((n + 1) + 1) se gère tranquille avec le binôme de Newton, ok
ça a l’air pas mal on valide.
p−1
(p) p+1 p + 1 (k)
Supposons donc avoir (p + 1)Sn = (n + 1) −1− ∑( )Sn . On veut alors
k
k=0
montrer que :
p−1
(p) p+1 p + 1 (k)
(p + 1)Sn+1 = ((n + 1) + 1) −1−∑( )Sn+1 .
k
k=0

(k) (k) k
Bonne nouvelle on l’a dit Sn+1 = Sn +(n+1) donc déjà à gauche on peut se rapprocher
de ce qu’on avait au rang n en écrivant que :
(p) (p) p
(p + 1)Sn+1 = (p + 1)Sn + (p + 1)(n + 1) .

Bon maintenant on fait pareil de l’autre côté avec la somme avec des coefficients :
p−1 p−1
p + 1 (k) p+1 (k) k
∑( )Sn+1 = ∑ ( ) (Sn + (n + 1) )
k k
k=0 k=0
p−1 p−1
p + 1 (k) p+1 k
= ∑( )Sn + ∑ ( )(n + 1) .
k k
k=0 k=0

k
Ok donc là on a simplement fait ce qu’on disait : faire sortir les (n + 1) et se rapprocher
le plus possible de ce qu’on avait au rang n. Maintenant time d’utiliser le binôme de
Newton sur ce qui nous reste :
p+1
p+1 p+1 k
((n + 1) + 1) = ∑( )(n + 1) .
k
k=0

Mais là on voit que du coup le truc de droite du rang n + 1 va se simplifier ! On sait
qu’il vaut :
p+1 p−1 p−1
p+1 k p + 1 (k) p+1 k
∑( )(n + 1) − 1 − ∑ ( )Sn − ∑ ( )(n + 1) ,
k k k
k=0 k=0 k=0

soit :
p−1
p+1 p+1 p+1 p p + 1 (k)
(p + 1)(n + 1) + ( p )(n + 1) − 1 − ∑ ( )Sn ,
k
k=0
ÍÒÒ Ò Ò Ò Ò Ò Ò Ò ÒÑ Ò Ò Ò Ò Ò Ò Ò Ò Ò Ï ÍÒÒ Ò Ò Ò Ò Ò Ò Ò ÒÑ Ò Ò Ò Ò Ò Ò Ò Ò Ò Ï
=1 =p+1

6
càd :
p−1
p+1 p + 1 (k) p+1
(n + 1) −1−∑( )Sn + (p + 1)(n + 1) .
k
k=0
p
Donc finalement passer de n à n+1 ça va simplement rajouter (p+1)(n+1) au membre
p
de droite. Mais on l’a vu ça ajoute aussi juste (p + 1)(n + 1) au membre de gauche !
Donc ils restent égaux et on vient de chopper notre hérédité.

Ok alors cet exemple était particulièrement hard dans le sens où y a plein de sommes
partout et ça fait mal à la tête. Donc on essaye de rester calme, de voir sur qui ça semble
le plus simple notre récurrence, et de voir de chaque côté ce qui change par rapport au
rang n.

L’idée c’est qu’ici on a même pas besoin de comprendre nos sommes : c’est l’intérêt
d’une récurrence. Une fois qu’on sait sur qui faire notre récurrence, on va simplement
manipuler nos expressions pour se ramener à un truc qui ressemble au truc du rang n.

Bon après j’ai (un peu) menti : on ne va pas forcément toujours essayer de faire appa-
raitre le rang n de force dans le rang n + 1. Parfois on va plutôt travailler avec ce qu’on
veut montrer, et paf, magie, il va apparaitre de lui-même.

n k
+ x x
Example 7 Montrer par récurrence que pour tout x ∈ R on a e ≥ ∑ .
k!
k=0

Ok donc là on va plus partir de ce que l’on veut montrer on rang n + 1, c’est-à-dire :
2 n+1
x x x
e ≥1+x+ + ⋅⋅⋅ + .
2 (n + 1)!

C’est une fonction en x donc on va dériver la différence pour obtenir :

2 n
x x x
e −1−x− − ⋅⋅⋅ − .
2 n!
Ah mais ça c’est le rang n ! Par hypothèse de récurrence la dérivée de la différence est
+ +
positive sur R donc la différence est croissante sur R et finalement elle vaut 0 en 0
+
donc elle est bien positive sur R . Paf c’est fini !

Ici on a donc d’abord travaillé très naturellement possible avec le rang n + 1, avant de
voir le rang n apparaitre comme par magie.

Finalement un exo un peu différent, de type ”combinatoire”.

7
 ∗
Example 8 Pour tout n ∈ N on note Tn le nombre d’entiers naturels comportant n
chiffres et ne comportant pas la succession 13. On appelle un tel nombre nombre porte-
bonheur Montrer que :
√ √
3− 6 √ n 3+ 6 √ n
× (5 − 2 6) + × (5 + 2 6) .
6 6
Ok donc cette formule est absolument impénétrable et ne représente rien donc on va
l’oublier pour le moment. Ca semble déjà un miracle que ce soit un entier !

Regardons quelques exemples : pour n = 1 on a {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} qui marchent,

ok c’était simple.

Pour n = 2 tous les entiers entre 0 et 100 marchent sauf 13.

Pour n = 3 ça se complique. Regardons comment construire un chiffre vérifiant notre

propriété. Par exemple, que se passe-t-il une fois qu’on choisit le premier chiffre de notre
nombre ?

Si on met un 1 au tout début alors on est forcé de mettre un chiffre qui n’est pas 3
en deuxième position : on a 9 possibilités. Une fois ces deux chiffres choisis, le reste de
notre nombre a n − 2 chiffres et doit simplement ne pas contenir la succession 13.

Donc on a Tn−2 possibilités pour choisir le reste de notre nombre et 9 pour le deuxième
chiffre. On a ainsi 9Tn−2 nombres portes-bonheurs de taille n commençant par le chiffre 1.

Sinon on commence par un autre chiffre que 1 donc on aura pas de problème entre
le premier et le deuxième chiffre (càd pas de succession 13) et le reste de notre nombre
contient n − 1 chiffres et doit seulement former un nombre porte-bonheur de taille n − 1.
On a ainsi Tn−1 possibilités soit Tn−1 nombres porte-bonheur de taille n ne commençant
pas par le chiffre 1.

On en déduit finalement une relation de récurrence : Tn = Tn−1 + 9Tn−2 . Sauf qu’on

connait T1 qui vaut 10 et T2 qui vaut 99. On peut ainsi montrer, par récurrence que :
√ √
3− 6 √ n 3+ 6 √ n
Tn = × (5 − 2 6) + × (5 + 2 6) ,
6 6
ce qui représente un gros calcul que je ne ferai pas, mais on voit que ça se fait :p.

Ici du coup on essaye de construire un nombre porte-bonheur de taille n en se ra-

menant à des nombres porte-bonheur de taille plus petit. Pour ça on essaye de fixer les
premiers chiffres, et on improvise. On obtient finalement une formule de récurrence, et
ça, on sait faire ! L’important était de ne pas se laisser distraire par la formule moche,
et de voir comment construire un nombre porte-bonheur de taille n petit à petit.

8
 Finalement pour conclure j’aimerais préciser que parfois ça ne coute rien de supposer
les rangs 1, 2, . . . , n vrais pour montrer le rang n + 1 : c’est la même chose. On parle
simplement de récurrence forte mais c’est vraiment la même idée et quand on en a
besoin, ça se voit.
n n n−1 n−2 n−1
Exercice 1 Montrer que a − b = (a − b)(a +a b + ⋅⋅⋅ + b ).

Exercice 2 Montrer le binôme de Newton.

∗
Exercice
√ n 3 Montrer√ que pour tout n ∈ N il existe des entiers an et bn tels que
(1 + 5) = an + bn 5.

Retrouver ce résultat avec le binôme de Newton.

p
k n p n−1
Exercice 4 Montrer que ∑ (−1) (k ) = (−1) ( p ).
k=0

n
k 2 n(n + 1)
Exercice 5 Montrer que ∑ (−1) (n − k) = .
2
k=0

n
Exercice 6 Montrer que (n + 1)! ≥ ∑ k!.
k=1

2 2 2
Exercice 7 Montrer que 1 + 2 + 3 + ⋅ ⋅ ⋅ + n ≤ 2 − n1 .
n
Exercice 8 Démontrer que pour tout entier positif n, le nombre 10 − 1 est un multiple
de 9.
2n k+1 n
(−1) 1
Exercice 9 Montrer que pour n ≥ 1 on a ∑ =∑ .
k n+k
k=1 k=1

Exercice 10 Soit x un réel. On suppose que x + x1 ∈ Z. Montrer que pour tout entier
n ≥1:
n 1
x + n ∈ Z.
x
Exercice 11 On définit une suite (Sn ) par S1 = 1 et S2 = 2. Pour n ≥ 3 on pose
Sn = Sn−1 + (n − 1)Sn−2 .
√
Montrer que Sn ≥ n! pour n ≥ 1.
n n
Exercice 12 Soit x1 , . . . , xn des réels positifs. Montrer que ∏(1 + xi ) ≥ 1 + ∏ xi .
i=1 i=1

n n−1 n n
Exercice 13 Soit x, y des réels positifs. Montrer que (x + y) ≤ 2 (x + y ).

9
Exercice 14 Montrer que pour tout entier positif n :
n 3
3 ≥n .

Exercice 15 Montrer que pour tout entier positif n :

n n
4 (2n)! 4
√ ≤ 2
≤ √
3
.
2 n n! n
n+1 n
Exercice 16 Pour n ≥ 1 un entier, montrer que n ≥ (n + 1) .
∗
Exercice 17 Soit n, p ∈ N . Montrer que :
p+1

n p
∏(n + k)
k=1
∑ ∏(k + l) = .
p+1
k=0 l=1

10