Logique et raisonnement
Chapitre 01
MPSI (1re année) — Chapitre 01. Quantificateurs, implication, équivalence, raisonnement par récurrence, par l’absurde, par contraposition.
Ce chapitre a été réalisé conformément au programme marocain de mathématiques de la filière MPSI.
1 Opérations logiques élémentaires
1.1 La négation
À chaque expression A (affirmation – propriété – assertion) relative à un domaine donné, on associe la valeur « Vraie » ou « Fausse ». S’il s’agit de son contraire ou sa négation, on note \neg A.
Table de vérité de la négation :
| A | \neg A |
|---|---|
| V | F |
| F | V |
ou
| A | \neg A |
|---|---|
| 1 | 0 |
| 0 | 1 |
Exemple 1.1
Soit (x,a)\in\mathbb{R}^2.
- La négation de (x=a) est (x\neq a).
- La négation de (x>a) est (x\leq a).
- La négation de (quel que soit x de \mathbb{R}, x vérifie x^2\geq 0) est (il existe x de \mathbb{R} tel que x^2<0).
1.2 La conjonction
À partir de deux affirmations A et B, on peut former l’affirmation « A et B » que l’on note A \wedge B.
Table de vérité de la conjonction :
| A | B | A \wedge B |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
ou
| A | B | A \wedge B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
Exemple 1.2
Soit x\in\mathbb{C}.
- (x^2+x+1=0)\wedge(\operatorname{arg}(x)=\frac{2\pi}{3}) donne x=j=e^{i\frac{2\pi}{3}}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}.
1.3 La disjonction
À partir de deux affirmations A et B, on peut former l’affirmation « A ou B » que l’on note A \vee B.
Table de vérité de la disjonction :
| A | B | A \vee B |
|---|---|---|
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
ou
| A | B | A \vee B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Exemple 1.3
Soit x\in\mathbb{C}.
- (x^2-x=0) donne (x=0)\vee(x=1).
1.4 L’implication
À partir de deux affirmations A et B, on peut former l’affirmation « A implique B » que l’on note A \Longrightarrow B.
Table de vérité de l’implication :
| A | B | A \Longrightarrow B |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
ou
| A | B | A \Longrightarrow B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Exemple 1.4
- Dans \mathbb{C}, xy=0 \Longrightarrow (x=0)\vee(y=0).
1.5 L’équivalence
À partir de deux affirmations A et B, on peut former l’affirmation « A équivaut à B » que l’on note A \Leftrightarrow B.
Table de vérité de l’équivalence :
| A | B | A \Leftrightarrow B |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | V |
ou
| A | B | A \Leftrightarrow B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Exemple 1.5
- \left.\begin{array}{l}\text{M est un point}\\ \text{du cercle } \mathscr{C}(O,R)\end{array}\right\} \Leftrightarrow OM=R.
Remarque.
- \vee, \wedge, \Longrightarrow, \Leftrightarrow, NAND, XOR et NOR sont appelés aussi des connecteurs logiques.
- À partir de ces opérations logiques élémentaires, on peut former d’autres à savoir NAND, XOR, et NOR… etc.
- Ces opérations peuvent se traduire aussi par un calcul dans \mathbb{Z}/2\mathbb{Z}. Par exemple le « et » se traduit par la multiplication dans \mathbb{Z}/2\mathbb{Z} et XOR par la somme dans \mathbb{Z}/2\mathbb{Z}. Voici les opérations de calcul dans \mathbb{Z}/2\mathbb{Z} :
| \overset{\curvearrowright}{+} | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| \overset{\curvearrowright}{\times} | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Pour plus de détails, consultez les liens : lien 1 et lien 2.
1.6 Propriétés
Théorème 1.1
Soient A, B et C trois affirmations. Alors on a :
- \neg(\neg A) \equiv A
- A\wedge(B\wedge C) \equiv (A\wedge B)\wedge C (associativité de \wedge)
- A\vee(B\vee C) \equiv (A\vee B)\vee C (associativité de \vee)
- A\wedge B \equiv B \wedge A (commutativité de \wedge)
- A\vee B \equiv B \vee A (commutativité de \vee)
- A\wedge(B\vee C) \equiv (A\wedge B)\vee(A\wedge C) (distributivité)
- A\vee(B\wedge C) \equiv (A\vee B)\wedge(A\vee C) (distributivité)
- A\wedge A\equiv A
- A\vee A\equiv A
- \neg(A\vee B)\equiv(\neg A)\wedge(\neg B) (loi de Morgan)
- \neg(A\wedge B)\equiv(\neg A)\vee(\neg B) (loi de Morgan)
- A \Longrightarrow B \equiv (\neg A)\vee B
- A \Longrightarrow B \equiv ((\neg B) \Longrightarrow (\neg A)) (principe de la contraposée)
- A\Leftrightarrow B \equiv (A\Longrightarrow B)\wedge(B\Longrightarrow A) (principe de la double implication)
- (A \vee B)\Longrightarrow C\equiv (A \Longrightarrow C) \wedge (B\Longrightarrow C)
- \neg(A\Longrightarrow B) \equiv A\wedge(\neg B)
- \neg(A\Leftrightarrow B) \equiv (A\Leftrightarrow(\neg B)) \equiv ((\neg A) \Leftrightarrow B)
Proposition 1.1 — (Quelques tautologies)
Soient A, B et C trois affirmations. Les formules suivantes sont des tautologies :
- A \vee (\neg A) (principe du tiers exclu)
- A \Longrightarrow A
- A \equiv A
- A \Longrightarrow (A\vee B)
- (A\wedge B) \Longrightarrow A
- (A\wedge (A\Longrightarrow B))\Longrightarrow B
- (A\Longrightarrow B)\wedge(B\Longrightarrow C) \Longrightarrow (A\Longrightarrow C) (transitivité de \Longrightarrow)
Exercice 1.1
Nier les expressions suivantes :
- ((A\Longrightarrow B)\wedge C)\vee(\neg B)
- ((A\Longrightarrow B)\wedge C)\Longrightarrow B
Solution. Niions les expressions proposées :
- On a : \begin{aligned} \neg\left[((A\Longrightarrow B)\wedge C)\vee(\neg B)\right] &\equiv \neg\left[\left((A\Longrightarrow B)\vee(\neg B)\right)\wedge\left(C\vee(\neg B)\right)\right]\\ &\equiv \neg\left[\left(((\neg A)\vee B)\vee(\neg B)\right)\wedge\left(C\vee(\neg B)\right)\right]\\ &\equiv \neg\left(C\vee(\neg B)\right)\\ &\equiv (\neg C)\wedge B \end{aligned}
- On a : \begin{aligned} \neg(((A\Longrightarrow B)\wedge C)\Longrightarrow B) &\equiv \neg(\neg((A\Longrightarrow B)\wedge C)\vee B)\\ &\equiv ((A\Longrightarrow B)\wedge C)\wedge(\neg B)\\ &\equiv (((\neg A)\vee B)\wedge C)\wedge(\neg B)\\ &\equiv (((\neg A)\wedge C)\vee(B\wedge C))\wedge(\neg B)\\ &\equiv \left[(\neg A)\wedge C)\wedge(\neg B)\right]\vee\left[(B\wedge C)\wedge(\neg B)\right]\\ &\equiv (\neg A)\wedge C \wedge(\neg B) \end{aligned}
1.6.1 Quantificateurs
Soit \mathcal{R}(x) une assertion dépendant d’une variable x. On écrit (\exists x \,/\, \mathcal{R}(x)) pour dire qu’il existe au moins un des objets x pour lequel \mathcal{R}(x) est vraie.
Exemple 1.6
Soient f : \mathbb{R} \longrightarrow \mathbb{R} une fonction et (u_n)_{n\in\mathbb{N}} une suite à valeurs réelles.
- \forall \varepsilon >0, \exists \alpha >0 \, (\forall x\in\mathbb{R}) \, (|x-x_0|\leq \alpha \Longrightarrow |f(x)-f(x_0)|\leq \varepsilon) exprime la continuité de f en x_0.
- \exists \alpha >0, \forall \varepsilon >0 \, (\forall x\in\mathbb{R}) \, (|x-x_0|\leq \alpha \Longrightarrow |f(x)-f(x_0)|\leq \varepsilon) exprime que f est constante au voisinage de x_0.
- \forall \varepsilon >0, \exists N\in\mathbb{N} \, (\forall n\in\mathbb{N}) \, (n\geq N \Longrightarrow |u_n-a|\leq \varepsilon) exprime que la suite (u_n)_{n\in\mathbb{N}} converge vers l’élément a.
- \forall M\in\mathbb{R}, \exists n\in\mathbb{N}, \, u_n>M exprime le fait que (u_n)_{n\in\mathbb{N}} n’est pas majorée.
Proposition 1.2 — (Règles de distributivité)
Soient P(x) et Q(x) deux expressions dépendant d’une variable x. On a :
- \forall x,\ (P(x)\wedge Q(x))\equiv (\forall x,\ P(x))\wedge(\forall x,\ Q(x))
- \exists x,\ (P(x)\vee Q(x))\equiv (\exists x,\ P(x))\vee(\exists x,\ Q(x))
Exercice 1.2
A-t-on :
- \forall x,\ (P(x)\vee Q(x))\equiv (\forall x,\ P(x))\vee(\forall x,\ Q(x)) ?
- \exists x,\ (P(x)\wedge Q(x))\equiv (\exists x,\ P(x))\wedge(\exists x,\ Q(x)) ?
Proposition 1.3
Soit P(x) une expression dépendant d’une variable x et Q ne l’est pas. On a :
- \forall x,\ (P(x)\vee Q)\equiv (\forall x,\ P(x))\vee Q
- \exists x,\ (P(x)\wedge Q)\equiv (\exists x,\ P(x))\wedge Q
Proposition 1.4 — (Quantification d’une implication)
- Si la propriété P ne dépend pas de x :
- \forall x,\ (P \Longrightarrow Q(x)) \equiv P \Longrightarrow (\forall x,\ Q(x))
- \exists x,\ (P \Longrightarrow Q(x)) \equiv P \Longrightarrow (\exists x,\ Q(x))
- Si la propriété Q ne dépend pas de x :
- \forall x,\ (P(x) \Longrightarrow Q) \equiv (\forall x,\ P(x)) \Longrightarrow Q
- \exists x,\ (P(x) \Longrightarrow Q) \equiv (\forall x,\ P(x)) \Longrightarrow Q
Proposition 1.5 — (Négation des quantificateurs)
Soit P(x) une expression dépendant d’une variable x. On a :
- \neg(\forall x,\ P(x)) \equiv (\exists x,\ \neg P(x))
- \neg(\exists x,\ P(x)) \equiv (\forall x,\ \neg P(x))
1.7 Types de raisonnement
1.7.1 Raisonnement par les équivalences successives
Pour démontrer qu’une propriété P est vraie, on démontre des fois qu’elle est équivalente à une propriété qu’on sait vraie à l’avance.
Exemple 1.7
Soit (a,b)\in\mathbb{R}^2. Montrons que ab\leq \frac{a^2+b^2}{2} :
Procédons par des équivalences successives. On a : \begin{aligned} ab\leq \frac{a^2+b^2}{2} &\iff 2ab \leq a^2+b^2\\ &\iff a^2+b^2-2ab \geq 0\\ &\iff (a-b)^2\geq 0 \end{aligned} La dernière expression équivalente est vraie, on conclut alors que ab\leq \frac{a^2+b^2}{2}.
Exemple 1.8
Soit a\in\mathbb{C}\smallsetminus\{1\} et n\in\mathbb{N}. Montrons que \sum_{k=0}^n a^k=\frac{1-a^{n+1}}{1-a} :
Procédons par des équivalences successives. On a : \begin{aligned} \sum_{k=0}^n a^k=\frac{1-a^{n+1}}{1-a} &\iff (1-a)\sum_{k=0}^n a^k=1-a^{n+1}\\ &\iff \sum_{k=0}^n (1-a)a^k=1-a^{n+1}\\ &\iff \sum_{k=0}^n (a^k-a^{k+1})=1-a^{n+1}\\ &\iff a^0-a^{n+1}=1-a^{n+1} \end{aligned} D’où : \sum_{k=0}^n a^k=\frac{1-a^{n+1}}{1-a}.
1.8 Raisonnement par disjonction des cas
Pour démontrer qu’une propriété est vraie, on considère tous les cas possibles et on vérifie qu’elle est vraie dans chacun des cas possibles.
Exemple 1.9
On montre que pour tout n\in\mathbb{N}, n(n+1) est pair : soit n un entier naturel et considérons tous les cas possibles :
- Cas 1 : si n est pair alors il existe k\in\mathbb{N} tel que n=2k, donc n(n+1)=2k(2k+1)=2\times k(2k+1), et par suite, n(n+1) est pair.
- Cas 2 : si n est impair alors il existe k\in\mathbb{N} tel que n=2k+1, donc n(n+1)=(2k+1)(2k+2)=2\times(2k+1)(k+1), et par suite, n(n+1) est pair.
D’où n(n+1) est pair pour tout n de \mathbb{N}.
Exemple 1.10
Soit x\in\mathbb{R}. Montrons que x^2+x+1\geq 0.
- Cas 1 : si x\leq -1 alors x\leq 0 et x+1\geq 0, donc x(x+1)\leq 0 et par suite, x^2+x+1\geq 1>0.
- Cas 2 : si x\geq -1 alors x+1\geq 0 et x^2\geq 0, donc x^2+x+1\geq 0.
D’où : x^2+x+1\geq 0
1.8.1 Raisonnement par contre-exemple
Soit P(x) une propriété dépendant d’un paramètre x. Pour montrer que l’affirmation (\forall x,\ P(x)) est fausse, on démontre que sa négation (\exists x,\ \neg P(x)) est vraie.
Exemple 1.11
La propriété suivante est-elle vraie : « deux rectangles de même aire ont même périmètre » ?
Les rectangles de longueurs respectives 4\,m et 2\,m et de largeurs respectives 0{,}5\,m et 1\,m constituent un contre-exemple.
Exemple 1.12
L’affirmation (\forall x\in\mathbb{C},\ x^2\geq 0) est fausse puisque les nombres complexes i et j constituent des contre-exemples.
Exemple 1.13
L’affirmation (\forall (a,b)\in (\mathbb{R}^+)^2,\ \sqrt{a+b}=\sqrt{a}+\sqrt{b}) est fausse puisque a=9 et b=16 constituent un contre-exemple.
1.8.2 Raisonnement par l’absurde
Exemple 1.14
Soit z\in\mathbb{C}. Montrons que si z=0 alors \mathcal{R}e(z)=\mathcal{I}m(z)=0 :
Raisonnons par absurde en supposant que z=0 et (\mathcal{R}e(z)\neq 0 ou \mathcal{I}m(z)\neq 0).
z=0 donne \mathcal{R}e(z)=-i\mathcal{I}m(z), donc \left(\mathcal{R}e(z)\right)^2=-\left(\mathcal{I}m(z)\right)^2, et par suite, \left(\mathcal{R}e(z)\right)^2+\left(\mathcal{I}m(z)\right)^2=0. Or \mathcal{R}e(z)\neq 0 ou \mathcal{I}m(z)\neq 0 donc \left(\mathcal{R}e(z)\right)^2+\left(\mathcal{I}m(z)\right)^2>0. Contradiction.
Conclusion : si z=0 alors \mathcal{R}e(z)=\mathcal{I}m(z)=0.
Exemple 1.15
Soit n\in\mathbb{N}. Montrer que si n^2 est pair alors n l’est aussi :
Raisonnons par absurde en supposant que n^2 est pair et n ne l’est pas. Donc n est impair, et par suite, il existe k\in\mathbb{N} tel que n=2k+1, donc n^2=4k^2+4k+1=2(2k^2+2k)+1, donc n^2 est impair. Contradiction.
Conclusion : si n^2 est pair alors n est aussi pair.
Exemple 1.16
Soient a, b > 0. Montrons que si \frac{a}{1+a}=\frac{b}{1+b} alors a = b :
Raisonnons par absurde en supposant que \frac{a}{1+a}=\frac{b}{1+b} et a\neq b. Comme \frac{a}{1+a}=\frac{b}{1+b} alors a(1+b) = b(1+a) donc a+ab=b+ab d’où a=b. Cela conduit à une contradiction.
Conclusion : si \frac{a}{1+a}=\frac{b}{1+b} alors a = b.
Exemple 1.17
Soit (k,k')\in\mathbb{N}^2. Montrons par absurde que si kk'=1 alors k=k'=1 :
Supposons alors que kk'=1 et (k\neq 1 ou k'\neq 1).
- Si k=0 ou k'=0 alors kk'=0\neq 1. Contradiction.
- Sinon, comme (k\neq 1 ou k'\neq 1) alors (k\geq 2 ou k'\geq 2), donc kk'\geq 2, donc kk'\neq 1. Contradiction.
Conclusion : si kk'=1 alors k=k'=1.
Exemple 1.18
Considérons l’assertion \mathcal{P}(x) : « Il n’existe aucun x de \mathbb{R} tel que x^2\leq 4 et 1{,}5\leq \sqrt{|x|} ».
Supposons qu’il existe un tel x alors x^2\leq 4 et \underset{\simeq 5{,}06}{(1{,}5)^4}\leq |x|^2 : alors 4 est supérieur à 5, ce qui est impossible.
D’où la propriété \mathcal{P}(x) est vraie.
1.8.3 Raisonnement par contraposée
Comme on a déjà mentionné, l’implication A \Longrightarrow B se traduit par (\neg A)\vee B qui est la même chose que (\neg(\neg B))\vee(\neg A) et qui se traduit par (\neg B)\Longrightarrow(\neg A). A \Longrightarrow B \equiv (\neg B)\Longrightarrow(\neg A) Il s’agit alors dans le raisonnement par contraposée de démontrer l’implication équivalente.
Exemple 1.19
Soit n\in\mathbb{N}. Montrons que si n^2 est pair alors n l’est aussi :
Raisonnons par contraposée, supposons que n est impair et montrons que n^2 l’est aussi. Donc il existe un entier k\in\mathbb{N} tel que n=2k+1, par suite n^2=4k^2+4k+1=2(2k^2+2k)+1, d’où n^2 est impair.
Ainsi, si n^2 est pair alors n l’est aussi.
Exemple 1.20
Soit x\in\mathbb{R}. Montrons que si pour tout \varepsilon >0, |x|\leq \varepsilon alors x=0 :
Raisonnons par contraposée, supposons que x\neq 0 et montrons qu’il existe \varepsilon >0 tel que |x|> \varepsilon. Si on prend \varepsilon =\frac{|x|}{2}>0 alors |x|> \varepsilon.
D’où : \forall \varepsilon >0,\ |x|\leq \varepsilon \Longrightarrow x=0
Exemple 1.21
Soit n\in\mathbb{N}. Montrons que : \left(\forall m\in\mathbb{N},\ n^2-1\neq 8m\right)\Longrightarrow \left(\exists k\in\mathbb{N},\ n=2k\right) La contraposée s’écrit : \left(\forall k\in\mathbb{N},\ n\neq 2k\right)\Longrightarrow \left(\exists m\in\mathbb{N},\ n^2-1= 8m\right) Si on suppose \left(\forall k\in\mathbb{N},\ n\neq 2k\right) alors n est impair, donc il existe un entier k\in\mathbb{N} tel que n=2k+1, donc n^2=4k^2+4k+1=4k(k+1)+1. Or, k(k+1) est pair donc il existe m\in\mathbb{N} tel que k(k+1)=2m et par suite n^2=8m+1 donc n^2-1= 8m. D’où : \left(\forall m\in\mathbb{N},\ n^2-1\neq 8m\right)\Longrightarrow \left(\exists k\in\mathbb{N},\ n=2k\right)
Exemple 1.22
Soient x_1,\cdots,x_n (n\geq 1) et M des réels. Montrons que : x_1+\cdots+x_n=M \Longrightarrow \exists i\in \llbracket 1,n \rrbracket,\ x_i\geq \frac{M}{n} La contraposée s’écrit : \forall i\in \llbracket 1,n \rrbracket,\ x_i<\frac{M}{n} \Longrightarrow x_1+\cdots+x_n\neq M Donc \sum_{i=1}^n x_i<\sum_{i=1}^n\frac{M}{n}=M, par suite \sum_{i=1}^n x_i\neq M. D’où : x_1+\cdots+x_n=M \Longrightarrow \exists i\in \llbracket 1,n \rrbracket,\ x_i\geq \frac{M}{n}
1.9 Raisonnement par analyse-synthèse
Le raisonnement par analyse-synthèse est un type de raisonnement mathématique permettant de démontrer l’existence et l’unicité d’un objet vérifiant des propriétés données. Il se décompose en deux parties :
- L’analyse : on suppose que l’objet existe et on essaie de trouver des conditions nécessaires que doit vérifier cet objet. Ce faisant, on prouve que si l’objet existe, alors il est nécessairement égal à un certain objet x_0 (ceci assure l’unicité).
- La synthèse : on considère l’objet x_0 identifié dans la partie analyse, et on vérifie qu’il a bien les propriétés voulues (ceci assure l’existence).
Exemple 1.23
Montrons que toute application f: \mathbb{R}\longrightarrow \mathbb{R} s’écrit de façon unique comme somme d’une application paire et d’une autre impaire :
Soit f: \mathbb{R}\longrightarrow \mathbb{R} une application et procédons par analyse-synthèse :
Analyse : supposons qu’il existe deux applications g,h:\mathbb{R}\longrightarrow \mathbb{R} telles que g est paire, h est impaire et f=g+h. Donc pour x\in\mathbb{R}, on a : \begin{cases} f(x)=g(x)+h(x)\\ f(-x)=g(x)-h(x)\end{cases} Donc : \begin{cases} g(x)=\frac{1}{2}\left(f(x)+f(-x)\right)\\ h(x)=\frac{1}{2}\left(f(x)-f(-x)\right)\end{cases} D’où l’unicité de l’écriture.
Synthèse : pour x\in\mathbb{R}, posons : \begin{cases} g(x)=\frac{1}{2}\left(f(x)+f(-x)\right)\\ h(x)=\frac{1}{2}\left(f(x)-f(-x)\right)\end{cases} Alors on a bien :
- f=g+h
- g est paire
- h est impaire
D’où l’existence de l’écriture.
1.10 Raisonnement par récurrence
Théorème 1.2 — (Propriétés de \boldsymbol{\mathbb{N}})
L’ensemble des entiers naturels possède les propriétés suivantes :
- (N1) Toute partie non vide de \mathbb{N} possède un plus petit élément.
- (N2) Toute partie non vide de \mathbb{N} et majorée possède un plus grand élément.
- (N3) L’ensemble \mathbb{N} lui-même n’est pas majoré, en particulier il ne possède pas de plus grand élément.
Rappel : on dit qu’une partie D de \mathbb{R} est majorée s’il existe M\in\mathbb{R} tel que \forall x\in D,\ x\leq M.
1.10.1 Principe de récurrence
Si on se donne une propriété \mathcal{P}(n) dépendant d’un paramètre n\in\mathbb{N}, et il se trouve qu’elle est vraie à chaque fois qu’on prend un entier n\in\mathbb{N} au hasard, on se demande si elle est vraie pour tout n\in\mathbb{N}.
Par exemple : \mathcal{P}(n) : \quad 1+2+3+\cdots+(n-1)+n=\frac{n(n+1)}{2}
- Pour n=1 : 1=\frac{1(1+1)}{2} (\mathcal{P}(1) est vraie)
- Pour n=2 : 1+2=3=\frac{2(2+1)}{2} (\mathcal{P}(2) est vraie)
- Pour n=3 : 1+2+3=6=\frac{3(3+1)}{2} (\mathcal{P}(3) est vraie)
- Pour n=4 : 1+2+3+4=10=\frac{4(4+1)}{2} (\mathcal{P}(4) est vraie)
- etc.
La question qui se pose : existe-il un moyen qui assure que cela va être vrai pour tout n\in\mathbb{N} ? La réponse est positive : c’est le raisonnement par récurrence.
Théorème 1.3 — (Récurrence faible)
Soit \mathcal{P}(n) une propriété dépendant d’un paramètre n avec n\in\mathbb{N}. S’il existe n_0 \in\mathbb{N} tel que :
- (R1) \mathcal{P}(n_0) est vraie ;
- (R2) \forall n\geq n_0, (\mathcal{P}(n) \Longrightarrow \mathcal{P}(n+1)).
Alors \mathcal{P}(n) est vraie pour tout n\geq n_0.
Preuve. Raisonnons par absurde : supposons qu’il existe au moins un entier m\geq n_0 tel que \mathcal{P}(m) soit fausse.
Considérons l’ensemble : A =\{k\in\mathbb{N} \,/\, (k\geq n_0)\wedge (\mathcal{P}(k) \text{ fausse})\} A est une partie de \mathbb{N} non vide par hypothèse (car (m\geq n_0)\wedge(\mathcal{P}(m) \text{ fausse})) donc elle possède un plus petit élément m_0. On a \mathcal{P}(n_0) est vraie (d’après l’hypothèse (R1)) et \mathcal{P}(m_0) est fausse, donc m_0>n_0 par suite m_0>m_0-1\geq n_0. Or, m_0-1\notin A (car m_0 =\min A), donc \mathcal{P}(m_0-1) est vraie. Il en résulte que, d’après (R2), \mathcal{P}(m_0) est vraie puisque \mathcal{P}(m_0-1) est vraie. Ce qui contredit la définition de m_0. D’où le résultat, c’est-à-dire la propriété \mathcal{P}(n) est vraie pour tout n\geq n_0.
Remarque. La condition (R1) s’appelle l’initialisation et la condition (R2) s’appelle l’hérédité.
Exemple 1.24
Montrons par récurrence \forall n\geq 4,\ \left(\mathcal{P}(n) : n^2\leq 2^n\right) :
- (R1) Pour n=n_0=4, on a 4^2=16 \leq 2^4=16. Donc la propriété \mathcal{P}(n_0) est vraie.
- (R2) Soit n\geq 4. Supposons \left(\mathcal{P}(n) : n^2\leq 2^n\right) et montrons : \mathcal{P}(n+1) : (n+1)^2\leq 2^{n+1} On a n^2\leq 2^n donc 2n^2\leq 2^{n+1}. \text{Or, } (n+1)^2-2n^2=-n^2+2n+1 =-(n-1)^2+2\leq -7<0 puisque n\geq 4. Donc (n+1)^2 \leq 2n^2 \leq 2^{n+1} c’est-à-dire \mathcal{P}(n+1) est vraie.
Ainsi, d’après le théorème précédent, \forall n\geq 4, \left(\mathcal{P}(n) : n^2\leq 2^n\right) est vraie.
Exemple 1.25
Montrons par récurrence \forall n\geq 1,\ \left(\mathcal{P}(n) : \sum_{k=1}^n k=\frac{n(n+1)}{2}\right) :
- (R1) Pour n=1, on a \sum_{k=1}^1 k=1=\frac{1(1+1)}{2}. Donc la propriété \mathcal{P}(1) est vraie.
- (R2) Soit n\geq 1. Supposons \left(\mathcal{P}(n) : \sum_{k=1}^n k=\frac{n(n+1)}{2}\right) et montrons : \mathcal{P}(n+1) : \sum_{k=1}^{n+1} k=\frac{(n+1)(n+2)}{2} On a : \sum_{k=1}^{n+1} k=1+\cdots+n+(n+1)=\sum_{k=1}^n k+(n+1) Or d’après l’hypothèse de récurrence \sum_{k=1}^n k=\frac{n(n+1)}{2}, donc : \begin{aligned} \sum_{k=1}^{n+1} k&=\frac{n(n+1)}{2}+(n+1)\\ &=\frac{n(n+1)+2(n+1)}{2}\\ &=\frac{(n+1)(n+2)}{2} \end{aligned} Donc \mathcal{P}(n+1) est vraie. D’où : \forall n\geq 1,\ \left(\mathcal{P}(n) : \sum_{k=1}^n k=\frac{n(n+1)}{2}\right)
Exemple 1.26
Montrons par récurrence que \forall n\geq 1,\ \left(\mathcal{P}(n) : \sum_{k=1}^n (-1)^k k^2=(-1)^n\sum_{k=1}^n k\right) :
- (R1) Pour n=1, on a \sum_{k=1}^1 (-1)^k k^2=-1=(-1)^1\sum_{k=1}^1 k. Donc la propriété \mathcal{P}(1) est vraie.
- (R2) Soit n\geq 1. Supposons \mathcal{P}(n) et montrons : \mathcal{P}(n+1) : \sum_{k=1}^{n+1} (-1)^k k^2=(-1)^{n+1}\sum_{k=1}^{n+1} k On a : \sum_{k=1}^{n+1} (-1)^k k^2=\sum_{k=1}^n (-1)^k k^2+(-1)^{n+1}(n+1)^2 Or d’après l’hypothèse de récurrence : \sum_{k=1}^n (-1)^k k^2=(-1)^n\sum_{k=1}^n k=(-1)^n\frac{n(n+1)}{2}, donc : \begin{aligned} \sum_{k=1}^{n+1} (-1)^k k^2&=(-1)^n\frac{n(n+1)}{2}+(-1)^{n+1}(n+1)^2\\ &=(-1)^{n+1}\frac{n+1}{2}\left[-n+2(n+1)\right]\\ &=(-1)^{n+1}\frac{(n+1)(n+2)}{2}\\ &=(-1)^{n+1}\sum_{k=1}^{n+1} k \end{aligned} Donc \mathcal{P}(n+1) est vraie. D’où : \forall n\geq 1,\ \left(\mathcal{P}(n) : \sum_{k=1}^n (-1)^k k^2=(-1)^n\sum_{k=1}^n k\right)
Exemple 1.27
Soit (u_n)_{n\in\mathbb{N}} la suite numérique définie par : \begin{cases} u_0=1\\ \forall n\in\mathbb{N},\ u_{n+1}=\sum_{k=0}^n u_k\end{cases} Montrons par récurrence \forall n\in\mathbb{N}^*,\ \left(\mathcal{P}(n) : u_n=2^{n-1}\right) :
- (R1) Pour n=1, u_1=\sum_{k=0}^0 u_k=u_0=1=2^{1-1}, donc \mathcal{P}(1) est vraie.
- (R2) Soit n\in\mathbb{N}^*. Supposons \mathcal{P}(n) : u_n=2^{n-1} et montrons \mathcal{P}(n+1) : u_{n+1}=2^{n}. On a : u_{n+1}=\sum_{k=0}^n u_k=\sum_{k=0}^{n-1} u_k+u_n=2u_n Or d’après l’hypothèse de récurrence, u_n=2^{n-1} donc : u_{n+1}=2\times 2^{n-1}=2^n Donc \mathcal{P}(n+1) est vraie. D’où : \forall n\in\mathbb{N}^*,\ \left(\mathcal{P}(n) : u_n=2^{n-1}\right)
Théorème 1.4 — (Récurrence forte)
Soit \mathcal{P}(n) une propriété dépendant d’un paramètre n avec n\in\mathbb{N} et soit n_0\in\mathbb{N} tel que :
- (R1) \mathcal{P}(n_0) est vraie ;
- (R3) \forall n\geq n_0, \left((\forall k\in \llbracket n_0,n\rrbracket,\ \mathcal{P}(k))\Longrightarrow \mathcal{P}(n+1)\right).
Alors \mathcal{P}(n) est vraie pour tout n\geq n_0.
Preuve. Même démonstration que le théorème précédent.
Exemple 1.28 — (Théorème d’Euclide)
Montrons par récurrence, pour n\geq 2, la propriété \mathcal{P}(n) : n est produit de nombres premiers.
- (R1) 2 est produit de lui-même et 2 est premier, donc \mathcal{P}(2) est vraie.
- (R3) Soit n\geq 2. Supposons que \mathcal{P}(k) est vraie pour 2\leq k \leq n et montrons que la propriété est vraie pour n+1 : si n+1 est déjà un nombre premier, il est alors produit de lui-même. Sinon, il existe deux entiers a et b vérifiant 2\leq a,b \leq n et n+1=a\times b. D’après l’hypothèse (R3), a et b sont produits de nombres premiers, donc n+1 l’est aussi.
D’où pour tout n supérieur ou égal à 2, n est produit de nombres premiers.
Exemple 1.29
Soit (u_n)_{n\in\mathbb{N}} la suite numérique définie par : \begin{cases} u_0=1\\ \forall n\in\mathbb{N},\ u_{n+1}=\sum_{k=0}^n u_k\end{cases} Montrons par récurrence \forall n\in\mathbb{N}^*,\ \left(\mathcal{P}(n) : u_n=2^{n-1}\right) :
- (R1) Pour n=1, u_1=\sum_{k=0}^0 u_k=u_0=1=2^{1-1}, donc \mathcal{P}(1) est vraie.
- (R3) Soit n\in\mathbb{N}^*. Supposons : \forall k\in \llbracket 1,n\rrbracket,\ \mathcal{P}(k) : u_k=2^{k-1} et montrons \mathcal{P}(n+1) : u_{n+1}=2^{n}. On a : u_{n+1}=\sum_{k=0}^n u_k=1+\sum_{k=1}^n u_k Or d’après l’hypothèse de récurrence, \forall k\in \llbracket 1,n\rrbracket,\ u_k=2^{k-1} donc : u_{n+1}=1+\sum_{k=1}^n 2^{k-1}=1+\sum_{k=0}^{n-1} 2^k=1+2^n-1=2^n Donc \mathcal{P}(n+1) est vraie. D’où : \forall n\in\mathbb{N}^*,\ \left(\mathcal{P}(n) : u_n=2^{n-1}\right)
Exemple 1.30
Soit (u_n)_{n\in\mathbb{N}} la suite numérique définie par : \begin{cases} u_0=1\\ \forall n\in\mathbb{N},\ u_{n+1}=\frac{1}{n+1}\sum_{k=0}^n u_k^2\end{cases} Montrons par récurrence que \forall n\in\mathbb{N},\ \left(\mathcal{P}(n) : u_n=1\right) :
- (R1) Pour n=0, u_0=1, donc \mathcal{P}(0) est vraie.
- (R3) Soit n\in\mathbb{N}. Supposons : \forall k\in \llbracket 0,n\rrbracket,\ \mathcal{P}(k) : u_k=1 et montrons que \mathcal{P}(n+1) : u_{n+1}=1. On a : u_{n+1}=\frac{1}{n+1}\sum_{k=0}^n u_k^2 Or d’après l’hypothèse de récurrence, \forall k\in \llbracket 0,n\rrbracket,\ u_k=1 donc : u_{n+1}=\frac{1}{n+1}\sum_{k=0}^n 1=\frac{n+1}{n+1}=1 Donc \mathcal{P}(n+1) est vraie. D’où : \forall n\in\mathbb{N},\ \left(\mathcal{P}(n) : u_n=1\right)
Théorème 1.5 — (Récurrence finie)
Soit \mathcal{P}(n) une propriété dépendant d’un paramètre n avec n\in\mathbb{N}. S’il existe n_0,n_1 \in\mathbb{N} tel que :
- (R1) \mathcal{P}(n_0) est vraie ;
- (R4) pour un certain n vérifiant n_0\leq n \leq n_1-1, (\mathcal{P}(n) \Longrightarrow \mathcal{P}(n+1)).
Alors \mathcal{P}(n) est vraie pour tout n vérifiant n_0\leq n \leq n_1.
Preuve. Même démonstration que le théorème de la récurrence faible.
Remarque. Dans l’exemple suivant nous allons utiliser les nombres premiers, c’est pourquoi on rappelle ici deux de leurs propriétés. Soit p\in\mathbb{N} tel que p\geq 2.
- p est premier si et seulement si ses seuls diviseurs dans \mathbb{Z} sont -p,-1,1,p.
- p est premier si et seulement si : \forall (a,b)\in\mathbb{Z}^2,\ \left(p\,|\,ab \Longrightarrow (p\,|\,a)\vee(p\,|\,b)\right)
Exemple 1.31
Soit p un nombre premier. Montrons par récurrence sur k que : \forall k \in \{1,\cdots,p-1\},\ p\,|\,C_p^k \qquad \left(C_p^k=\frac{p!}{k!(p-k)!}\right)
- (R1) Pour k=1, C_p^1=p qui est divisible par p.
- (R4) Soit k\in \{1,\cdots,p-2\}, supposons que p\,|\,C_p^k. Montrons que p\,|\,C_p^{k+1}, on a : C_p^{k+1}=\frac{p!}{(k+1)!(p-(k+1))!}=\frac{p-k}{k+1}\frac{p!}{k!(p-k)!}=\frac{p-k}{k+1}C_p^k \iff (k+1)C_p^{k+1}=(p-k)C_p^k Comme par hypothèse p\,|\,C_p^k alors p\,|\,(k+1)C_p^{k+1}. Or, p ne divise pas k+1 et p est premier donc p divise C_p^{k+1}. D’où, d’après le théorème de la récurrence finie, \forall k \in \{1,\cdots,p-1\},\ p\,|\,C_p^k.
Théorème 1.6 — (Récurrence multiple)
Soient \mathcal{P}(n) une propriété dépendant d’un paramètre n\in\mathbb{N} et q\in\mathbb{N}. S’il existe n_0 \in\mathbb{N} tel que :
- (R5) \mathcal{P}(n_0), \mathcal{P}(n_0+1),\cdots,\mathcal{P}(n_0+q-1) sont toutes vraies ;
- (R6) \forall n\geq n_0, (\mathcal{P}(n), \mathcal{P}(n+1),\cdots,\mathcal{P}(n+q-1) \text{ vraies} \Longrightarrow \mathcal{P}(n+q) \text{ vraie}).
Alors \mathcal{P}(n) est vraie pour tout n vérifiant n\geq n_0.
Preuve. Démonstration par l’absurde : supposons qu’il existe m\in\mathbb{N} vérifiant m>n_0 et \mathcal{P}(m) est fausse. Considérons alors l’ensemble : A=\{ n\in\mathbb{N} \,/\, (n>n_0)\wedge(\mathcal{P}(n) \text{ fausse}) \} A est une partie non vide (puisque m\in A) de \mathbb{N}, donc elle admet un plus petit élément m_0. On a alors \mathcal{P}(m_0) est fausse donc m_0\notin \{n_0,n_0+1,\cdots,n_0+q\} (car d’après (R5), \mathcal{P}(n_0),\cdots,\mathcal{P}(n_0+q-1) sont toutes vraies) donc m_0>n_0+q-1. On a alors : m_0-q,m_0-q+1,\cdots,m_0-2,m_0-1 \notin A \quad \text{et} \quad \forall n\in\{m_0-q,\cdots,m_0-1\},\ n\geq n_0 donc \mathcal{P}(m_0-q),\mathcal{P}(m_0-q+1),\cdots,\mathcal{P}(m_0-1) sont toutes vraies. On applique alors (R6) aux q propriétés \mathcal{P}(m_0-q),\cdots,\mathcal{P}(m_0-1) pour obtenir \mathcal{P}(m_0) est vraie, ce qui contredit la définition de m_0. D’où, l’hypothèse de départ est fausse. Par conséquent, \mathcal{P}(n) est vraie pour tout n vérifiant n\geq n_0.
Exemple 1.32
Soit (u_n)_{n\in\mathbb{N}} la suite définie par : \begin{cases} u_0=2,\ u_1=3\\ \forall n\in\mathbb{N},\ u_{n+2}=3u_{n+1}-2u_n\end{cases} Montrons par récurrence double que \forall n\in\mathbb{N},\ \mathcal{P}(n) : u_n=2^n+1. On a :
- (R5) \mathcal{P}(0) : u_0=2=2^0+1 vraie et \mathcal{P}(1) : u_1=3=2^1+1 vraie.
- (R6) Soit n\in\mathbb{N}. Supposons \left(\mathcal{P}(n) : u_n=2^n+1\right) et \left(\mathcal{P}(n+1) : u_{n+1}=2^{n+1}+1\right) vraies et montrons \left(\mathcal{P}(n+2) : u_{n+2}=2^{n+2}+1\right) vraie. On a : \begin{aligned} u_{n+2}&=3u_{n+1}-2u_n\\ &=3(2^{n+1}+1)-2(2^n+1)\\ &=3\cdot 2^{n+1}+3-2\cdot 2^{n}-2\\ &=3\cdot 2^{n+1}+1-2^{n+1}\\ &=2\cdot 2^{n+1}+1\\ &=2^{n+2}+1 \end{aligned} D’où (\mathcal{P}(n+2) : u_{n+2}=2^{n+2}+1). Par conséquent, \forall n\in\mathbb{N},\ u_n=2^n+1.
Théorème 1.7 — (Récurrence partielle)
Soit \mathcal{P}(n) une propriété dépendant d’un paramètre n\in\mathbb{N}. Si on a :
- (R1) \mathcal{P}(1) est vraie ;
- (R7) \forall n\in\mathbb{N},\ n=2^k\ (k\in\mathbb{N}^*),\ (\mathcal{P}(n)\Longrightarrow \mathcal{P}(2n)).
Alors \mathcal{P}(n) est vraie pour toute puissance entière de 2.
Preuve. Démonstration par l’absurde : supposons qu’il existe l\geq 1 tel que \mathcal{P}(2^l) ne soit pas vraie. Considérons l’ensemble : A=\{k\in\mathbb{N} \,/\, k\geq 1 \text{ et } \mathcal{P}(2^k) \text{ fausse}\} A est une partie de \mathbb{N} non vide (puisque l\in A), donc A admet un plus petit élément k_0. On a alors \mathcal{P}(n) vraie pour n=2^{k_0-1}. D’autre part, d’après (R7), \mathcal{P}(2n) est vraie c’est-à-dire que \mathcal{P}(2^{k_0}) est vraie. Or, k_0 \in A donc \mathcal{P}(2^{k_0}) est fausse. Ce qui est absurde. D’où, l’hypothèse de départ est fausse et par suite \mathcal{P}(n) est vraie pour toute puissance entière de 2.
Théorème 1.8 — (Récurrence descendante)
Soit \mathcal{P}(n) une propriété dépendant d’un paramètre n\in\mathbb{N}. Si on a :
- (R8) \mathcal{P}(n) est vraie sur un sous-ensemble infini de \mathbb{N} ;
- (R9) \forall n\in\mathbb{N}^*,\ (\mathcal{P}(n)\Longrightarrow \mathcal{P}(n-1)).
Alors \mathcal{P}(n) est vraie pour tout n de \mathbb{N}.
Preuve. Remarquons que (R9) peut être formulée autrement : (*)\qquad \forall n\in\mathbb{N},\ \left(\mathcal{P}(n)\Longrightarrow(\forall k\in \llbracket 0,n\rrbracket,\ \mathcal{P}(n-k))\right) Ceci est obtenu sans problème en faisant une récurrence finie sur k : en effet, soit n\in\mathbb{N} tel que \mathcal{P}(n) soit vraie et considérons (R9), montrons que \forall k\in \llbracket 0,n\rrbracket,\ \mathcal{P}(n-k) est vraie.
- (R1) Pour k=0, \mathcal{P}(n) est vraie ;
- (R4) Soit k\in \llbracket 0,n-1\rrbracket tel que \mathcal{P}(n-k) soit vraie et montrons que \mathcal{P}(n-(k+1)) est vraie. D’après (R9), \mathcal{P}(n-(k+1)) est vraie. D’où la formulation (*) de (R9).
Démonstration par absurde du théorème : soit A un sous-ensemble infini de \mathbb{N} tel que \forall n\in A, \mathcal{P}(n) est vraie et supposons qu’il existe m de \mathbb{N} tel que \mathcal{P}(m) soit fausse. Comme A est infini alors il existe l de A tel que l\geq m. Posons k=l-m donc m=l-k. Comme l\in A donc \mathcal{P}(l) est vraie et d’après (*) on aura \mathcal{P}(l-k) est vraie c’est-à-dire que \mathcal{P}(m) est vraie. Ce qui contredit la définition de m. D’où \mathcal{P}(n) est vraie pour tout n de \mathbb{N}.
Exemple 1.33 — (Utilisation de la récurrence partielle et descendante)
Montrons par récurrence que : \forall n \in\mathbb{N}^*,\ \mathcal{P}(n) : \forall x_1,\cdots,x_n>0,\quad \overset{\underbrace{\textbf{Moyenne géométrique}}}{(x_1 x_2\cdots x_n)^{\frac{1}{n}}}\leq \overset{\underbrace{\textbf{Moyenne arithmétique}}}{\frac{x_1+\cdots+x_n}{n}}
Étape 1 : montrons, en utilisant la récurrence partielle, que \mathcal{P}(n) est vraie pour tout n de la forme n=2^k (k\in\mathbb{N}) :
- (R1) Pour n=2^0=1 : x_1=x_1^{\frac{1}{1}}\leq \frac{x_1}{1}=x_1, \mathcal{P}(1) est vraie. Pour n=2^1=2 : soit x_1,x_2>0. On a : \frac{(x_1-x_2)^2}{4}\geq 0 \iff \frac{x_1^2+x_2^2-2x_1x_2}{4}\geq 0 \iff \frac{x_1^2+x_2^2+2x_1x_2}{4}\geq x_1x_2 donc \frac{(x_1+x_2)^2}{4}\geq x_1x_2 donc (x_1 x_2)^{\frac{1}{2}}\leq \frac{x_1+x_2}{2}. D’où \mathcal{P}(2) est vraie.
- (R7) Soit k\in\mathbb{N} tel que \mathcal{P}(n) soit vraie avec n=2^k, montrons alors que \mathcal{P}(2n) est vraie. Soient x_1,\cdots,x_{2n} des réels positifs, on a : (x_1\cdots x_n x_{n+1}\cdots x_{2n})^{\frac{1}{2n}}=\left[(x_1\cdots x_n)^{\frac{1}{n}}(x_{n+1}\cdots x_{2n})^{\frac{1}{n}}\right]^{\frac{1}{2}} On applique \mathcal{P}(2) pour y_1=(x_1\cdots x_n)^{\frac{1}{n}} et y_2=(x_{n+1}\cdots x_{2n})^{\frac{1}{n}}, donc : \left[(x_1\cdots x_n)^{\frac{1}{n}}(x_{n+1}\cdots x_{2n})^{\frac{1}{n}}\right]^{\frac{1}{2}}=(y_1 y_2)^{\frac{1}{2}}\leq \frac{y_1+y_2}{2}=\frac{(x_1\cdots x_n)^{\frac{1}{n}}+(x_{n+1}\cdots x_{2n})^{\frac{1}{n}}}{2} D’autre part, d’après \mathcal{P}(n) appliquée à x_1,\cdots, x_n et à x_{n+1},\cdots, x_{2n}, on a : (x_1\cdots x_n)^{\frac{1}{n}}\leq \frac{x_1+\cdots+x_n}{n} \quad \text{et} \quad (x_{n+1}\cdots x_{2n})^{\frac{1}{n}}\leq \frac{x_{n+1}+\cdots+x_{2n}}{n} Donc : (x_1\cdots x_{2n})^{\frac{1}{2n}} \leq \frac{(x_1\cdots x_n)^{\frac{1}{n}}+(x_{n+1}\cdots x_{2n})^{\frac{1}{n}}}{2} \leq \frac{\frac{x_1+\cdots+x_n}{n}+\frac{x_{n+1}+\cdots+x_{2n}}{n}}{2} Donc : (x_1\cdots x_{2n})^{\frac{1}{2n}} \leq \frac{x_1+\cdots+x_n +x_{n+1}+\cdots+x_{2n}}{2n} D’où \mathcal{P}(2n). Par conséquent, \forall n=2^k\ (k\in\mathbb{N}), \mathcal{P}(n) est vraie.
Étape 2 : montrons, en utilisant la récurrence descendante (puisque \mathcal{P}(n) est vraie sur l’ensemble A=\{2^k \,/\, k\in\mathbb{N}\} qui est infini), que \mathcal{P}(n) est vraie pour tout n de \mathbb{N}^* :
- (R8) La propriété \mathcal{P}(n) est vraie sur A qui est une partie de \mathbb{N} infinie.
- (R9) Supposons \mathcal{P}(n) vraie pour n\geq 2 et montrons que \mathcal{P}(n-1) est vraie : soient des réels x_1,\cdots,x_{n-1}>0. Posons z=\frac{x_1+\cdots+x_{n-1}}{n-1}. (R9) appliquée aux n éléments x_1,\cdots,x_{n-1},z donne : (x_1\cdots x_{n-1}z)^{\frac{1}{n}} \leq \frac{x_1+\cdots+x_{n-1}+z}{n}=\frac{(n-1)z+z}{n}=z Donc (x_1\cdots x_{n-1}z)\leq z^n, donc (x_1\cdots x_{n-1})\leq z^{n-1}. D’où : (x_1\cdots x_{n-1})^{\frac{1}{n-1}}\leq \frac{x_1+\cdots+x_{n-1}}{n-1} Ainsi, on a montré \mathcal{P}(n-1).
Conclusion : \forall n\in\mathbb{N}^*,\ \forall x_1,\cdots,x_n>0,\quad (x_1 x_2\cdots x_n)^{\frac{1}{n}}\leq \frac{x_1+\cdots+x_n}{n}