Chapitre IV. Groupe B 1.

Première partie : Arithmétique et Combinatoire

1 Première partie : Arithmétique et Combinatoire

1 Récurrence (Paul)
Introduction
Dans ce cours, on découvre un nouvel outil, très utile pour démontrer un résultat dépen-
dant d’une variable n ∈ N. Cet outil s’appelle le théorème de récurrence et il provient direc-
tement de la théorie axiomatique des entiers naturels. cette dernière ayant donné lieu à de
nombreuses constructions, nous nous contenterons de démontrer le théorème de récurrence
pour l’une d’entre elles.

Théorie axiomatique des entiers naturels et théorème de récurrence

Nous abordons ici l’étude du théorème de récurrence via la théorie axiomatique des en-
tiers naturels de Peano. Nous postulons l’existence d’un triplet (0, N, S), où N est un en-
semble, 0 un élément de cet ensemble et S : N → N est une application vérifiant :

Axiome 1.
S est injective

Axiome 2.
L’image de S est N − {0}

Axiome 3.
Si A est une partie de N, telle que 0 ∈ A et (∀n ∈ N)(n ∈ A) =⇒ (S(n) ∈ A), alors A = N

Ce troisième axiome est appelé axiome de récurrence, on appelle l’application S, l’appli-

cation successeur. Avec cette théorie nous pouvons énoncer et démontrer le théorème dit de
récurrence :

Théorème 4.
de récurrence
Soit P (n), une assertion dépendant d’une variable n ∈ N. Alors les relations P (0) (ce
qui veut dire que l’assertion est vraie pour n = 0) et ∀n ∈ N, P (n) =⇒ P (S(n)) impliquent
∀n ∈ N, P (n) (ce qui veut dire que l’assertion est vraie pour tous les entiers naturels).

Démonstration. Soit A l’ensemble {n, n ∈ NetP (n)} ; A est non vide car 0 ∈ A. Par hypothèse,
n ∈ A =⇒ S(n) ∈ A ; d’après l’axiome 3, il s’ensuit A = N 
La deuxième hypothèse signifie que la l’assertion P (n) est héréditaire. Ainsi le théorème
de récurrence nous dit que si une assertion P (n) est héréditaire et initialisé (c’est à dire vraie
en 0), alors est vraie pour tout n ∈ N. On dégage ainsi une méthode pour démontrer une
assertion de type P (n) :

[Link] : On montre P (0).

2.Hérédité : En prenant un n quelconque, on montre que P (n) =⇒ P (n + 1).

104
Chapitre IV. Groupe B 1. Première partie : Arithmétique et Combinatoire

[Link] du théorème : On a toutes les hypothèses du théorème, on peut donc

l’appliquer et conclure.

Exercice 1
Montrer par récurrence que pour tout n ≥ 1,
n
X Xn
3
k =( k)2 ,
k=1 k=1
Pn
Bonus : Soit alors (uk )k≥1 , une suite de réels strictement positifs tels que k=1 u3k =
( nk=1 uk )2 , montrer que pour tout k ≥ 1, xk = k.
P

Exercice 2
Montrer par récurrence que pour tout n ≥ 1, 2n−1 ≤ n! ≤ nn .

Exercice 3
Montrer par récurrence que pour tout entier n et tout réel x > 0, (1 + x)n ≥ 1 + nx.

Exercice 4
n


Pour tout k 6 n ∈ N définit le coefficient binomial k
de façon récurrente :
Ç å Ç å
n n
= =1
0 n
Ç å Ç å Ç å
n+1 n n
= + pour tous k < n
k+1 k k+1
1. Montrer que Ç å
n n!
=
k k!(n − k)!

2. Montrer que
n Ç å
X n k n−k
(a + b)n = a b
k=0
k

3. Calculer
n Ç å
X 2n
k=0
2k

Récurrence forte
Théorème 5.
récurrence forte
Soit P (n), une assertion dépendant d’une variable n ∈ N. Alors les relations P (0) et ∀n ∈
N, (∀k ≤ n P (k)) =⇒ P (n + 1) impliquent ∀n ∈ N, P (n).

105
Chapitre IV. Groupe B 1. Première partie : Arithmétique et Combinatoire

Démonstration. Cela revient à montrer par récurrence simple la propriété (∀k ≤ n P (k)). 
Les étapes de preuves restent alors les mêmes avec une modification de l’étape d’hérédité.
Exercice 5
Montrer par récurrence forte que tout entier supérieur ou égal à deux admet une unique
décomposition en facteur premier

Exercice 6
Démontrer par récurrence forte que tout entier n ≥ 1 s’écrit de façon unique de la forme
2p (2q + 1), où p et q sont des entiers

Exercice 7
Démontrer par récurrence forte que tout entier n ≥ 1 peut s’écrire comme somme de puis-
sances de 2 toutes distinctes.

Exercices

Exercice 8
Trouver une expression comparable à celle du binôme de Newton pour (x1 + x2 + ... + xm )n .

Exercice 9
n
Soit k un entier naturel impair, montrer que 2n+2 divise k 2 − 1 pour tout n ≥ 1.

Exercice 10
f : I → R convexe, montrer que pour tout a1 , ...an ∈ I et pour tout λ1 , ..., λn ∈ [0, 1] tels
Soit P
que ni=1 λi = 1, montrer que
Xn n
X
f( λi ai ) ≤ λi f (ai ).
i=1 i=1

Corrections
Solution de l’exercice 1

Rappel 6.
n
X n(n + 1)
k= .
k=1
2

Vous pouvez vérifiez ce résultat par récurrence ou alors être bien plus malin...

Montrons donc par récurrence sur n que

n
X n2 (n + 1)2
k3 = .
k=1
4

106
Chapitre IV. Groupe B 1. Première partie : Arithmétique et Combinatoire

Pour n = 1, c’est vrai car

12 (1 + 1)2
13 = .
4
Supposons la propriété vraie au rang n, et montrons-la au rang n + 1. On a
n+1
X Xn
k3 = ( k 3 ) + (n + 1)3
k=1 k=1

par relation de Chasles, soit

n+1
X n2 (n + 1)2
k3 = + (n + 1)3
k=1
4

par hypothèse de récurrence, ainsi

n+1
X (n + 1)2 (n2 + 4n + 4)
k3 = ,
k=1
4

n+1
X
3(n + 1)2 (n + 2)2
k = .
k=1
4
Ce qui clôt la récurrence.
Solution de l’exercice 2
Montrons par récurrence sur n ∈ N∗ que

2n−1 ≤ n! ≤ nn .

Pour n = 1, c’est vrai car

21−1 = 1 = 1! = 11
Supposons la propriété vraie au rang n, et montrons-la au rang n + 1. On a comme n ≥ 1,
n + 1 ≥ 2, d’où
2n = 2 × 2n−1 ≤ 2 × n! ≤ (n + 1)!.
Ce qui clôt la récurrence pour l’inégalité de gauche, l’hypothèse de récurrence nous donne en
multipliant par n + 1

(n + 1)! ≤ (n + 1)nn ≤ (n + 1)(n + 1)n = (n + 1)n+1 .

Ce qui termine l’exercice.

Solution de l’exercice 3
Montrons par récurrence que pour tout entier n et tout réel x > 0,

(1 + x)n ≥ 1 + nx.

Pour n = 0, c’est vrai car

(1 + x)0 = 1 ≥ 1.

107
Chapitre IV. Groupe B 1. Première partie : Arithmétique et Combinatoire

Supposons la propriété vraie au rang n, et montrons-la au rang n + 1. On a,

(1 + x)n+1 = (1 + x)n (1 + x) ≥ (1 + nx)(1 + x) = 1 + (n + 1)x + nx2 ≥ 1 + (n + 1)x

Ce qui clôt la récurrence.

Solution de l’exercice 4
1. Montrons par récurrence sur n que, pour tout entier k < n,

Ç å
n n!
= .
k k!(n − k)!

Pour n = 0, c’est vrai car

Ç å
0 0!
=1= .
0 0!0!

Supposons la propriété vraie au rang n, et montrons-la au rang n + 1. Si k = 0 ou k = n + 1,

c’est vrai, car par exemple pour k = 0 on a

Ç å
n+1 (n + 1)!
=1= .
0 0!(n + 1)!

Supposons donc k non nul. Alors,

Ç å Ç å Ç å
n+1 n n
= + par définition
k k−1 k
n! n!
= + par hypothèse de récurrence
(k − 1)!(n − k + 1)! k!(n − k)!
ï ò
n! 1 1
= +
(k − 1)!(n − k)! n − k + 1 k
ï ò
n! n+1
=
(k − 1)!(n − k)! k(n − k + 1)
(n + 1)!
= ,
k!(n − k + 1)!

ce qui clôt la récurrence.

2. Montrons ce résultat par récurrence sur n. Pour n = 0 c’est évident. Supposons le résul-

108
Chapitre IV. Groupe B 1. Première partie : Arithmétique et Combinatoire

tat vrai au rang n, et montrons le au rang n + 1. On a :

(a + b)n+1 = (a + b)(a + b)n

n Ç å
X n k n−k
= (a + b) a b par hypothèse de récurrence
k=0
k
n Ç å n Ç å
X n k+1 n−k X n k n−k+1
= a b + a b
k=0
k k=0
k
n+1 Ç å n Ç å
X n X n k n−k+1
= ak bn−k+1 + a b
k=1
k−1 k=0
k
n ñÇ å Ç åô
n n
X n n
=a +b + + ak bn−k+1
k=1
k−1 k
n+1 Ç å
X n + 1 k n−k+1
= a b ,
k=0
k

ce qui clôt la récurrence.

3.
n Ç å n−1 Ç å Ç å
X 2n X 2n − 1 2n − 1
=2+ +
k=0
2k k=1
2k − 1 2k
2n−2 Ç
X 2n − 1
å
=2+
i=1
i
2n−1 Ç
X 2n − 1
å
=
i=0
i
= 22n−1 d’après la question précédente.

Solution de l’exercice 5
Théorème fondamental de l’arithmétique
Solution de l’exercice 6
Montrons par récurrence forte que tout entier n ≥ 1 s’écrit de la forme 2p (2q + 1), où p et q
sont des entiers.
Pour n = 1, c’est vrai en prenant p = q = 0.
Supposons maintenant que tout entier inférieur ou égal à n − 1 vérifie cette assertion et mon-
trons alors que l’entier n la vérifie. On a soit n pair, c’est à dire n = 2k avec 1 ≤ k ≤ n − 1. On
peut donc appliquer l’hypothèse de récurrence à k, qui nous assure donc l’existence de p et q
tel que k = 2p (2q + 1). Il s’ensuit n = 2k = 2p+1 (2q + 1), le couple d’entier (p + 1, q) convient
alors et clôt la preuve de l’existence pour n pair.
Si n est impair, alors par définition il existe q tel que n = 2q + 1. Dans ce cas là le couple (0, q)
convient et on a pas besoin de l’hypothèse de récurrence.
Montrons l’unicité d’une telle décomposition ; on suppose qu’il existe deux couples (p, q) et
(u, v) tels que pour n ∈ N∗ ,
n = 2p (2q + 1) = 2u (2v + 1),

109
Chapitre IV. Groupe B 1. Première partie : Arithmétique et Combinatoire

alors sans perte de généralité, on peut supposer p ≥ u, on a alors

2p−u (2q + 1) = 2v + 1.

Comme le membre de droite est impair, on a directement p = u et par suite q = v.

Solution de l’exercice 7
Montrons par récurrence forte que tout entier n ≥ 1 peut s’écrire comme somme de puis-
sances de 2 toutes distinctes.
Pour n = 1, c’est vrai car 20 = 1.
Supposons maintenant que tout entier inférieur ou égal à n − 1 vérifie cette assertion et mon-
trons alors que l’entier n la vérifie. On a soit n pair, c’est à dire n = 2k avec 1 ≤ k ≤ n − 1. On
peut donc appliquer l’hypothèse de récurrence à k, ce qui nous donne l’existence d’entiers
a1 , ..., aj tous distincts tels que
k = 2a1 + ... + 2aj ,
alors
n = 2a1 +1 + ... + 2aj +1
s’écrit bien comme somme de puissances de 2 toutes distinctes.
Si n est impair alors n − 1 = 2k avec 1 ≤ k ≤ n − 1. On peut donc appliquer l’hypothèse de
récurrence à k, ce qui nous donne l’existence d’entiers a1 , ..., aj tous distincts tels que

k = 2a1 + ... + 2aj ,

soit
n = 1 + 2a1 +1 + ... + 2aj +1 = 20 + 2a1 +1 + ... + 2aj +1 .
Ce qui clôt la récurrence.
Solution de l’exercice 8
Nous allons montrer par récurrence sur m que
Ç å
X n
(x1 + x2 + ... + xm ) =n
xk1 xk2 ...xkmm
k1 +k2 +...+km =n
k1 , k2 , ..., km 1 2

avec Ç å
n n!
=
k1 , k2 , ..., km k1 !k2 !...km !
. Pour m = 2 on retrouve la formule du binôme de Newton. Supposons alors que la formule
soit vraie pour m, on a donc :
Ç å
X n km−1
n
(x1 + ... + (xm + xm+1 )) = xk11 xk22 ...xm−1 (xm + xm+1 )K
k +k +...+K=n
k1 , k2 , ..., K
1 2

avec la formule du binôme sur (xm + xm+1 )K on a :

Ç å Ç å
X n km−1
X K k
= xk11 xk22 ...xm−1 xkm x m+1
k +k +...+K=n
k ,
1 2k , ..., K k
km , km+1 m m+1
1 2 m +km+1 =K

110
Chapitre IV. Groupe B 1. Première partie : Arithmétique et Combinatoire

Et par définition des coefficients, on a

Ç åÇ å Ç å
n K n! n! n! n
= = =
k1 , k2 , ..., K km , km+1 k1 !k2 !...K! km !km+1 ! k1 !k2 !...km+1 ! k1 , ..., km , km+1

Enfin :
Ç å
X n km+1
(x1 + x2 + ... + xm + xm+1 )n = xk11 xk22 ...xm+1
k1 +...+km+1 =n
k1 , k2 , ..., km , km+1

Solution de l’exercice 9
n
Soit k un entier naturel impair, montrons par récurrence que 2n+2 divise k 2 − 1 pour tout
n≥1
Pour n = 1, c’est vrai car k 2 − 1 = (k − 1)(k + 1) est divisible par 8 étant donné que k − 1 et
k + 1 sont deux nombres pairs dont l’un est divisible par 4. Supposons la propriété vraie au
n+1
rang n, et montrons-la au rang n + 1. Il faut montrer que 2n+3 divise k 2 − 1. On remarque
que
n+1 n n
k 2 − 1 = (k 2 − 1)(k 2 + 1).
D’après l’hypothèse de récurrence
n
2n+2 |k 2 − 1
n
et comme k est impair, k 2 + 1 est divisible par 2. Ce qui clôt la récurrence.
Solution de l’exercice 10
Inégalité de Jensen pour les fonctions convexes.

2 Divisibilité, PGCD et nombres premiers (Ilyès)

Cours
On s’appuie sur les résultats montrés dans le cours de Jean-Louis Tu, disponible sur ce
lien Arithmétique niveau 1. On utilisera plus précisément les résultats concernant :
1. toute la partie "2-Divisibilité"
2. la partie "4.1-Identités remarquables" uniquement

Exercices

Exercice 1
21n + 4
Montrer que pour tout entier strictement positif n, la fraction est irréductible.
14n + 3
Exercice 2
Trouver tous les entiers naturels n tels que : n5 − 2n4 − 7n2 − 7n + 3 = 0

Exercice 3
Trouver tous les entiers strictement positifs n tels que pour tout entier a impair, si a2 6 n alors
a | n.

111