Carrieretudes · Classes préparatoires · MPSI / MP2I · Semestre 1

Mathématiques MPSI

Le programme de mathématiques du premier semestre de prépa, de la logique jusqu'au calcul matriciel. Chaque chapitre suit le même trajet : un cours rigoureux avec ses démonstrations, une fiche méthode qui dit quoi faire devant un énoncé, puis un TD complet aux exercices gradués et entièrement corrigés.

13 chapitres39 blocs128 exercices de TD corrigés

CoursDéfinitions, théorèmes, démonstrations à ouvrir, vrai ou faux pour vérifier.

MéthodesLes réflexes à avoir devant chaque type de question, avec un exemple rédigé.

TDUne feuille de TD de prépa : énoncés gradués, indications, corrigés rédigés.

Ta progressionCoche « Compris » sur chaque bloc : ta progression est enregistrée et visible dans le sommaire.

★application directe du cours★★exercice classique★★★type concours★★★★approfondissement

Partie 1

Fondements

Le langage commun de toutes les mathématiques de prépa : logique, ensembles, applications, et le calcul algébrique sans lequel rien ne tient.

Chapitre 1

Logique et raisonnements

3 blocs · Cours → Méthodes → TD

1.1Cours Compris

1.1

Logique et modes de raisonnement

Notions : assertions, connecteurs, quantificateurs, négation, contraposée, absurde, analyse-synthèse, récurrences simple, double et forte

Cours

Assertions et connecteurs logiques

Une assertion (ou proposition) est un énoncé mathématique dont on peut dire qu'il est vrai ou faux, sans ambiguïté. « $2 + 2 = 4$ » est une assertion vraie, « $\sqrt{2} \in Q$ » une assertion fausse. Un énoncé qui dépend d'une variable, comme « $x \geq 0$ », est un prédicat : il devient une assertion quand on fixe $x$ .

Définition Connecteurs

À partir de deux assertions $P$ et $Q$ , on construit : la négation $\neg P$ (« non $P$ »), la conjonction $P \land Q$ (« $P$ et $Q$ »), la disjonction $P \lor Q$ (« $P$ ou $Q$ », ou inclusif), l'implication $P \Rightarrow Q$ et l'équivalence $P \Leftrightarrow Q$ . Leurs valeurs de vérité sont données par la table ci-dessous.

$P$	$Q$	$\neg P$	$P \land Q$	$P \lor Q$	$P \Rightarrow Q$	$P \Leftrightarrow Q$
V	V	F	V	V	V	V
V	F	F	F	V	F	F
F	V	V	F	V	V	F
F	F	V	F	F	V	V

L'implication $P \Rightarrow Q$ est donc fausse dans un seul cas : $P$ vraie et $Q$ fausse. En particulier, une implication dont l'hypothèse est fausse est vraie. Par définition, $P \Rightarrow Q$ a la même table que $(\neg P) \lor Q$ . On dit que $P$ est une condition suffisante pour $Q$ , et que $Q$ est une condition nécessaire pour $P$ .

Proposition Règles de calcul

Pour toutes assertions $P, Q, R$  :

double négation : $\neg (\neg P) \Leftrightarrow P$  ;
lois de De Morgan : $\neg (P \land Q) \Leftrightarrow (\neg P) \lor (\neg Q)$ et $\neg (P \lor Q) \Leftrightarrow (\neg P) \land (\neg Q)$  ;
distributivité : $P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R)$ et $P \lor (Q \land R) \Leftrightarrow (P \lor Q) \land (P \lor R)$  ;
négation d'une implication : $\neg (P \Rightarrow Q) \Leftrightarrow P \land \neg Q$  ;
contraposée : $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$  ;
double implication : $(P \Leftrightarrow Q) \Leftrightarrow ((P \Rightarrow Q) \land (Q \Rightarrow P))$ .

Démonstration

Chaque équivalence se vérifie sur une table de vérité à 4 ou 8 lignes. Par exemple pour la contraposée : équivaut à , c'est-à-dire à , qui est exactement . Pour la négation de l'implication : par De Morgan.

Attention

La réciproque de $P \Rightarrow Q$ est $Q \Rightarrow P$  : elle n'a aucune raison d'être vraie ( $x = 2 \Rightarrow x^{2} = 4$ est vraie, la réciproque est fausse). La contraposée $\neg Q \Rightarrow \neg P$ , elle, est toujours équivalente à l'implication de départ. Et la négation de « $P \Rightarrow Q$ » n'est pas une implication : c'est « $P$ et non $Q$ ».

Quantificateurs

Définition Quantificateurs

Soit $P (x)$ un prédicat portant sur les éléments $x$ d'un ensemble $E$ .

$\forall x \in E, P (x)$ signifie : pour tout élément $x$ de $E$ , $P (x)$ est vraie.
$\exists x \in E, P (x)$ signifie : il existe au moins un élément $x$ de $E$ tel que $P (x)$ soit vraie.
$\exists! x \in E, P (x)$ signifie : il existe un et un seul tel $x$ .

La variable quantifiée est muette : $\forall x \in R, x^{2} \geq 0$ et $\forall t \in R, t^{2} \geq 0$ disent la même chose. En revanche, l'ordre des quantificateurs de natures différentes compte.

Exemple L'ordre change tout

« $\forall x \in R, \exists y \in R, y > x$ » est vraie (prendre $y = x + 1$  : $y$ dépend de $x$ ). « $\exists y \in R, \forall x \in R, y > x$ » est fausse : elle affirme qu'un même réel $y$ est plus grand que tous les réels, y compris lui-même. On peut toujours échanger deux $\forall$ consécutifs, ou deux $\exists$ consécutifs, mais jamais un $\forall$ et un $\exists$ .

Proposition Négation d'une assertion quantifiée

\neg (\forall x \in E, P (x)) ⟺ \exists x \in E, \neg P (x) \neg (\exists x \in E, P (x)) ⟺ \forall x \in E, \neg P (x)

Pour nier une assertion, on échange les $\forall$ et les $\exists$ sans changer leur ordre, puis on nie le prédicat final.

Exemple Nier une définition

« La suite $(u_{n})$ est majorée » s'écrit $\exists M \in R, \forall n \in N, u_{n} \leq M$ . Sa négation, « $(u_{n})$ n'est pas majorée », s'écrit $\forall M \in R, \exists n \in N, u_{n} > M$ . Pour une fonction $f : R \to R$ , « $f$ est croissante » s'écrit $\forall (x, y) \in R^{2}, x \leq y \Rightarrow f (x) \leq f (y)$ , et « $f$ n'est pas croissante » s'écrit $\exists (x, y) \in R^{2}, x \leq y et f (x) > f (y)$ . Attention : « non croissante » ne veut pas dire « décroissante ».

Les modes de raisonnement

Raisonnement direct. Pour montrer $P \Rightarrow Q$ , on suppose $P$ vraie et on en déduit $Q$ . La rédaction commence par « Supposons $P$ . » ou « Soit $x$ tel que… ».

Par contraposée. Pour montrer $P \Rightarrow Q$ , on montre $\neg Q \Rightarrow \neg P$ . Exemple : si $n^{2}$ est pair, alors $n$ est pair. Contraposée : si $n$ est impair, $n = 2 k + 1$ , alors $n^{2} = 2 (2 k^{2} + 2 k) + 1$ est impair.

Par l'absurde. Pour montrer $P$ , on suppose $\neg P$ et on aboutit à une contradiction.

Théorème Irrationalité de $\sqrt{2}$

$\sqrt{2}$ n'est pas un nombre rationnel.

Démonstration

Par l'absurde, supposons avec , , et la fraction irréductible. Alors est pair, donc est pair (contraposée ci-dessus) : . Il vient , soit , donc est pair aussi. Alors divise et , ce qui contredit l'irréductibilité.

Théorème Euclide

Il existe une infinité de nombres premiers.

Démonstration

Par l'absurde, supposons qu'il n'y en ait qu'un nombre fini . Posons . admet un diviseur premier (son plus petit diviseur est premier), qui est l'un des . Alors divise et , donc divise leur différence  : contradiction.

Disjonction de cas. Pour montrer $P$ , on sépare en cas qui recouvrent toutes les possibilités (par exemple $n$ pair / $n$ impair, $x \geq 0$ / $x < 0$ ).

Analyse-synthèse. Pour déterminer tous les objets vérifiant une propriété, on procède en deux temps. Analyse : on suppose qu'un objet convient et on accumule des conditions nécessaires, jusqu'à n'avoir plus qu'un petit nombre de candidats. Synthèse : on vérifie quels candidats conviennent réellement.

Proposition Fonctions paires et impaires

Toute fonction $f : R \to R$ s'écrit de manière unique $f = p + i$ avec $p$ paire et $i$ impaire.

Démonstration

Analyse. Si convient, alors . En ajoutant et soustrayant avec , on obtient et  : il y a au plus une décomposition (unicité).

Synthèse. Les fonctions et ainsi définies sont respectivement paire et impaire, et  : la décomposition existe. Exemple : .

Le raisonnement par récurrence

Axiome Principe de récurrence

Soit $n_{0} \in N$ et $P (n)$ un prédicat défini pour $n \geq n_{0}$ . Si $P (n_{0})$ est vraie (initialisation) et si, pour tout $n \geq n_{0}$ , $P (n) \Rightarrow P (n + 1)$ (hérédité), alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Ce principe est équivalent à une propriété fondamentale de $N$  : **toute partie non vide de $N$ admet un plus petit élément**. On l'admet.

Exemple Une récurrence simple

Montrons que pour tout $n \in N^{*}$ , $\sum_{k = 1}^{n} k = \frac{n (n + 1)}{2}$ . Notons $P (n)$ cette égalité. Initialisation : pour $n = 1$ , les deux membres valent $1$ . Hérédité : soit $n \geq 1$ tel que $P (n)$ soit vraie. Alors $\sum_{k = 1}^{n + 1} k = \frac{n (n + 1)}{2} + (n + 1) = \frac{(n + 1) (n + 2)}{2}$ , c'est $P (n + 1)$ . Conclusion : $P (n)$ est vraie pour tout $n \geq 1$ .

Théorème Récurrences double et forte

Récurrence double : si $P (n_{0})$ et $P (n_{0} + 1)$ sont vraies, et si pour tout $n \geq n_{0}$ , $(P (n) \land P (n + 1)) \Rightarrow P (n + 2)$ , alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Récurrence forte : si $P (n_{0})$ est vraie, et si pour tout $n \geq n_{0}$ , $(P (n_{0}) \land \dots \land P (n)) \Rightarrow P (n + 1)$ , alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Démonstration

Pour la récurrence forte, on applique la récurrence simple au prédicat  : « est vraie pour tout ». est , vraie. Si est vraie, l'hypothèse donne , donc . Ainsi est vraie pour tout , et a fortiori . La récurrence double se traite de même avec .

Exemple Récurrence forte : décomposition en facteurs premiers

Tout entier $n \geq 2$ est un produit de nombres premiers. Si c'est vrai pour tous les entiers de $[[2, n]]$ , considérons $n + 1$  : soit il est premier (c'est un produit à un facteur), soit $n + 1 = a b$ avec $2 \leq a, b \leq n$ , et il suffit de multiplier les décompositions de $a$ et de $b$ , qui existent par hypothèse. Une récurrence simple ne suffirait pas : on a besoin de $P (a)$ et $P (b)$ , pas de $P (n)$ .

Attention

Une hérédité qui ne fonctionne pas pour tous les $n$ ruine la preuve. Le célèbre « tous les chevaux ont la même couleur » échoue au passage de $n = 1$ à $n = 2$  : les deux groupes de $n$ chevaux utilisés n'ont alors aucun cheval en commun.

Vrai ou faux ? Réponds avant d'ouvrir.

P

est fausse, alors

P \Rightarrow Q

est vraie, quelle que soit

Q

Vrai. C'est la troisième et la quatrième ligne de la table de vérité. « Si , alors je suis le pape » est une implication vraie.

La négation de «

\forall ε > 0, \exists N \in N, \forall n \geq N, | u_{n} | \leq ε

» est «

\forall ε > 0, \exists N, \forall n \geq N, | u_{n} | > ε

».

Faux. On n'a pas échangé les quantificateurs. La négation correcte est .

(P \Rightarrow Q)

est équivalente à

(\neg Q \Rightarrow \neg P)

Vrai. C'est la contraposée ; les deux ont la même table de vérité.

Pour montrer qu'une propriété est vraie pour tout

n

, il suffit de la vérifier pour

n = 0, 1, 2, \dots, 10

Faux. Aucun nombre fini de vérifications ne remplace une preuve. est premier pour , mais pas pour  : .

1.2Méthodes Compris

1.2

Fiche méthode · Rédiger un raisonnement

Notions : choisir le type de raisonnement, rédiger une récurrence, nier proprement, analyse-synthèse

Fiche méthode

Méthode Nier une phrase quantifiée

Écrire la phrase avec des symboles, dans l'ordre exact où les variables sont introduites.
Changer chaque $\forall$ en $\exists$ et chaque $\exists$ en $\forall$ , sans toucher à l'ordre ni aux domaines ( $\forall ε > 0$ devient $\exists ε > 0$ ).
Nier le prédicat final : $\leq$ devient $>$ , « et » devient « ou », $A \Rightarrow B$ devient $A$ et $\neg B$ .

Méthode Choisir son type de raisonnement

La conclusion est une négation (« n'est pas rationnel », « n'existe pas », « est infini ») : penser à l'absurde.
L'hypothèse est plus simple à exploiter niée que la conclusion (« si $n^{2}$ est pair… ») : penser à la contraposée.
On demande « déterminer toutes les fonctions / tous les réels tels que… » : analyse-synthèse, et ne jamais oublier la synthèse.
On montre une propriété indexée par $n \in N$  : récurrence. Si $P (n + 1)$ se ramène à $P (n)$ et $P (n - 1)$ (suite définie par une relation à deux termes), récurrence double ; s'il faut des rangs quelconques plus petits (diviseurs, découpages), récurrence forte.
Une propriété dépend de la parité, du signe, d'une valeur absolue : disjonction de cas.

Méthode Rédiger une récurrence

Énoncer le prédicat : « Pour $n \in N$ , notons $P (n)$  : … ». Le prédicat ne contient pas « pour tout $n$ ».
Initialisation : vérifier $P (n_{0})$ explicitement (et $P (n_{0} + 1)$ pour une récurrence double).
Hérédité : « Soit $n \geq n_{0}$ tel que $P (n)$ soit vraie. Montrons $P (n + 1)$ . » Repérer où l'hypothèse de récurrence est utilisée.
Conclure : « Par récurrence, $P (n)$ est vraie pour tout $n \geq n_{0}$ . »

Exemple Rédaction type : une inégalité par récurrence

Montrons que $2^{n} \geq n^{2}$ pour tout $n \geq 4$ . Pour $n \geq 4$ , notons $P (n)$  : $2^{n} \geq n^{2}$ . Initialisation : $2^{4} = 16 = 4^{2}$ . Hérédité : soit $n \geq 4$ tel que $2^{n} \geq n^{2}$ . Alors $2^{n + 1} = 2 \cdot 2^{n} \geq 2 n^{2}$ , et il suffit de voir que $2 n^{2} \geq (n + 1)^{2}$ , c'est-à-dire $n^{2} - 2 n - 1 \geq 0$ , soit $(n - 1)^{2} \geq 2$ , vrai pour $n \geq 3$ . Donc $P (n + 1)$ est vraie, et par récurrence $P (n)$ est vraie pour tout $n \geq 4$ .

Méthode Analyse-synthèse : le squelette

Analyse. « Soit $f$ une solution. » Spécialiser l'hypothèse sur des valeurs bien choisies ( $x = 0$ , $y = x$ , $y = - x$ , $x = 1$ …) jusqu'à obtenir une expression explicite de $f$ , ou une liste finie de candidats.
Synthèse. « Réciproquement, soit $f$ l'une des fonctions trouvées. » Vérifier qu'elle satisfait l'énoncé dans tous les cas, pas seulement pour les valeurs utilisées dans l'analyse.
Conclure par « L'ensemble des solutions est … ».

Attention Erreurs classiques

Utiliser dans l'hérédité $P (n + 1)$ , c'est-à-dire ce qu'on veut démontrer.
Écrire le prédicat « $P (n)$  : pour tout $n$ , … » : la variable $n$ est alors muette et la récurrence ne veut plus rien dire.
Conclure une analyse sans synthèse : on a seulement trouvé des conditions nécessaires.
Confondre « $P$ est nécessaire pour $Q$ » ( $Q \Rightarrow P$ ) et « $P$ est suffisante pour $Q$ » ( $P \Rightarrow Q$ ).

1.3TD Compris

1.3

TD · Logique et raisonnements

10 exercices corrigés (3 ★ · 4 ★★ · 2 ★★★ · 1 ★★★★) · Cherche au moins 15 minutes au brouillon avant l'indication, et rédige avant d'ouvrir le corrigé.

TD · Travaux dirigés

Niveau

Exercice 1★Négations

Écrire avec des quantificateurs, puis nier, les assertions suivantes ( $f : R \to R$ , $(u_{n})$ suite réelle).

$f$ est bornée.
$f$ s'annule au moins une fois.
$f$ est strictement croissante.
La suite $(u_{n})$ est stationnaire (constante à partir d'un certain rang).
$f$ est périodique.

Indication

Commence par écrire chaque assertion avec des symboles. Pour la périodicité, il existe une période .

Corrigé détaillé

. Négation : .
. Négation : .
. Négation : .
. Négation : (la suite change de valeur infiniment souvent).
. Négation : .

Les domaines des variables (, ) ne sont pas niés : seul le prédicat final l'est.

Exercice 2★L'ordre des quantificateurs

Dire si chaque assertion est vraie ou fausse, en justifiant.

$\forall x \in R, \exists y \in R, x + y = 0$ .
$\exists y \in R, \forall x \in R, x + y = 0$ .
$\forall n \in N, \exists m \in N, m < n$ .
$\exists m \in N, \forall n \in N, m \leq n$ .
$\forall x \in R_{+}^{*}, \exists y \in R_{+}^{*}, y < x$ .

Indication

Dans « », le peut dépendre de . Dans « », un seul doit convenir pour tous les .

Corrigé détaillé

Vraie : pour donné, convient.
Fausse : si un tel existait, donnerait et donnerait . Négation vraie : (prendre ).
Fausse : pour , aucun entier naturel ne vérifie .
Vraie : convient. C'est l'existence d'un plus petit élément de .
Vraie : convient. En revanche « » est fausse (prendre ) : n'a pas de plus petit élément.

Exercice 3★Somme des cubes

Montrer par récurrence que pour tout $n \in N^{*}$  :

\sum_{k = 1}^{n} k^{3} = {(\frac{n (n + 1)}{2})}^{2} .

En déduire que la somme des cubes des $n$ premiers entiers est le carré de leur somme.

Indication

Dans l'hérédité, factorise dans .

Corrigé détaillé

Pour , notons l'égalité. Initialisation : . Hérédité : supposons pour un . Alors

c'est . Par récurrence, l'égalité est vraie pour tout . Comme , on a bien .

Exercice 4★★Inégalité de Bernoulli

Montrer que pour tout réel $x \geq - 1$ et tout $n \in N$ , $(1 + x)^{n} \geq 1 + n x$ .
Où l'hypothèse $x \geq - 1$ sert-elle ? Montrer que l'inégalité peut être fausse pour $x < - 1$ .
En déduire que si $q > 1$ , la suite $(q^{n})$ n'est pas majorée.

Indication

Dans l'hérédité, multiplie l'hypothèse de récurrence par  : il faut que ce facteur soit positif.

Corrigé détaillé

Fixons et notons  : . s'écrit . Si est vraie, comme , on peut multiplier l'inégalité par sans changer son sens :

D'où , et le résultat par récurrence.

L'hypothèse sert à multiplier par . Pour et  : et , égalité ; pour  : . L'inégalité est fausse.
Écrivons avec . Alors . Pour tout , il existe tel que (prendre ), donc  : la suite n'est pas majorée.

Exercice 5★★Quelques irrationnels

Montrer que $\ln 2 / \ln 3$ est irrationnel.
Montrer que $\sqrt{2} + \sqrt{3}$ est irrationnel.
Soit $r \in Q^{*}$ et $x \notin Q$ . Montrer que $r + x$ et $r x$ sont irrationnels. La somme de deux irrationnels est-elle toujours irrationnelle ?

Indication

Une égalité devient  : parité. 2. Élève au carré, puis isole  ; montre d'abord que comme pour .

Corrigé détaillé

Par l'absurde, supposons avec (le quotient est strictement positif). Alors , donc . Le membre de gauche est pair (), celui de droite impair : contradiction.
Montrons d'abord . Si irréductible, est pair, donc , puis  : est pair donc est pair, contradiction. Supposons maintenant . Alors , donc  : contradiction.
Si , alors , contradiction. Si , alors (car ), contradiction. La somme de deux irrationnels peut être rationnelle : .

Exercice 6★★Écriture en base 2

Montrer par récurrence forte que tout entier $n \geq 1$ s'écrit comme une somme de puissances de 2 deux à deux distinctes. (On montrera l'unicité de cette écriture au chapitre d'arithmétique.)

Indication

Pour , considère la plus grande puissance et applique l'hypothèse à , s'il est non nul. Pourquoi la puissance n'apparaît-elle pas dans l'écriture de ce reste ?

Corrigé détaillé

Pour , notons  : « est somme de puissances de 2 deux à deux distinctes ».  : .

Soit tel que soient vraies. Soit le plus grand entier tel que (il existe car et ). On a donc . Posons . Si , convient. Sinon , et par hypothèse avec des distincts. Comme , chaque , donc . Alors est une somme de puissances distinctes : est vraie.

Par récurrence forte, est vraie pour tout . Une récurrence simple ne suffirait pas : on utilise avec quelconque entre et .

Exercice 7★★Une équation fonctionnelle

Déterminer toutes les fonctions $f : R \to R$ telles que

\forall (x, y) \in R^{2}, f (x) f (y) - f (x y) = x + y .

Indication

Analyse : prends pour obtenir les valeurs possibles de , puis avec quelconque.

Corrigé détaillé

Analyse. Soit une solution. Avec  : , donc . Avec et quelconque : , soit .

Si , on obtient pour tout  : absurde (prendre ).
Donc , et pour tout  : .

Synthèse. Pour  : . La fonction convient.

Conclusion. L'unique solution est .

Exercice 8★★★Suite de Fibonacci

On définit $F_{0} = 0$ , $F_{1} = 1$ et $F_{n + 2} = F_{n + 1} + F_{n}$ pour $n \in N$ . On note $φ = \frac{1 + \sqrt{5}}{2}$ et $ψ = \frac{1 - \sqrt{5}}{2}$ .

Vérifier que $φ$ et $ψ$ sont les racines de $x^{2} = x + 1$ .
Montrer par récurrence double que $F_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}$ pour tout $n \in N$ (formule de Binet).
Montrer que $F_{n} \geq φ^{n - 2}$ pour tout $n \geq 1$ .
Montrer la formule de Cassini : $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ pour $n \geq 1$ .
En déduire que deux termes consécutifs $F_{n}$ et $F_{n + 1}$ n'ont aucun diviseur commun autre que $\pm 1$ .

Indication

Utilise , et de même pour . 3. Récurrence double aussi, avec . 4. Récurrence simple : écris en remplaçant par .

Corrigé détaillé

et  : ce sont les racines de .
 : .  : . Si la formule est vraie aux rangs et  :

et . Si et , alors . La suite croît donc au moins géométriquement.
Pour  : . Supposons . Alors

Si divise et , il divise , donc .

Exercice 9★★★Principe des tiroirs et divisibilité

Soit $n \geq 1$ et $A$ une partie de $[[1, 2 n]]$ à $n + 1$ éléments.

Montrer que tout entier $m \geq 1$ s'écrit de façon unique $m = 2^{k} q$ avec $k \in N$ et $q$ impair.
Montrer que $A$ contient deux entiers distincts dont l'un divise l'autre.
Le résultat reste-t-il vrai avec $n$ éléments ?

Indication

Associe à chaque élément de sa « partie impaire » . Combien de valeurs impaires possibles dans  ? Principe des tiroirs : si l'on range objets dans tiroirs, un tiroir contient au moins deux objets.

Corrigé détaillé

Existence : est le plus grand entier tel que divise (il existe car borne ), et est impair par maximalité. Unicité : si avec , alors serait pair : absurde. Donc et .
À chaque , associons sa partie impaire , un impair de . Il n'y a que impairs dans cet intervalle, et a éléments : par le principe des tiroirs (raisonnement par l'absurde : si les étaient deux à deux distincts, il y aurait impairs distincts dans un ensemble à éléments), il existe dans avec . Alors et avec , disons  : divise .
Non : a éléments, et si sont dans , , donc ne divise pas .

Exercice 10★★★★Récurrence de Cauchy : inégalité arithmético-géométrique

Pour $n \geq 1$ , on note $P (n)$  : « pour tous réels $x_{1}, \dots, x_{n} \geq 0$ , $\sqrt[n]{x_{1} \dots x_{n}} \leq \frac{x_{1} + \dots + x_{n}}{n}$ ».

Montrer $P (2)$ .
Montrer que $P (n) \Rightarrow P (2 n)$ . En déduire $P (2^{k})$ pour tout $k \in N$ .
Montrer que $P (n + 1) \Rightarrow P (n)$ pour $n \geq 1$ . On pourra appliquer $P (n + 1)$ à $x_{1}, \dots, x_{n}$ et $x_{n + 1} = m$ , où $m = \frac{x_{1} + \dots + x_{n}}{n}$ .
Conclure que $P (n)$ est vraie pour tout $n \geq 1$ . Quel principe de raisonnement a-t-on utilisé ?
Application : montrer que $n! \leq {(\frac{n + 1}{2})}^{n}$ .

Indication

Coupe les nombres en deux paquets de , applique à chaque paquet, puis aux deux moyennes. 4. Pour quelconque, choisis tel que et redescends.

Corrigé détaillé

Pour  : .
Soit . Notons , , et pour . Par , et . Alors

en utilisant . Comme est trivial, une récurrence sur donne pour tout .

Supposons et soit , leur moyenne. Appliquons à  : leur moyenne vaut , donc . Si , on divise par  : , c'est . Si , tous les sont nuls et l'inégalité est triviale.
Soit et tel que . est vraie, et en appliquant fois la question 3, on descend jusqu'à . C'est la récurrence de Cauchy (ou récurrence « en avant-arrière ») : une suite infinie de rangs où la propriété est vraie, plus une hérédité descendante.
Appliquons à  : , d'où .

Méthodes à retenir

Nier mécaniquement : on échange ∀ et ∃ sans changer l'ordre, puis on nie le prédicat.
Choisir la récurrence (simple, double, forte) selon les rangs dont l'hérédité a besoin.
Un « déterminer tous les » appelle une analyse-synthèse, synthèse comprise.
Une conclusion négative (irrationnel, impossible, infini) appelle l'absurde.

Mathématiques MPSI · semestre 1 — Chapitre 1

Mathématiques MPSI

Fondements

Logique et raisonnements

Logique et modes de raisonnement

Assertions et connecteurs logiques

Quantificateurs

Les modes de raisonnement

Le raisonnement par récurrence

Fiche méthode · Rédiger un raisonnement

TD · Logique et raisonnements

Méthodes à retenir

Continuer le cours