Démonstration et logique formelle

Une proposition est une affirmation qui peut être, sans ambiguïté, soit vraie, soit fausse. Elle ne peut pas être les deux à la fois et ne peut pas être ni l'un ni l'autre.

Exemples de propositions :

• "2 + 2 = 4" (Vraie)
• "Paris est la capitale de l'Allemagne" (Fausse)
• "Tous les chats sont noirs" (Fausse)

Exemples de phrases qui ne sont PAS des propositions :

• "Quel temps fait-il ?" (C'est une question)
• "Va chercher le pain." (C'est un ordre)
• "Cette phrase est fausse." (Paradoxe, ne peut être ni vraie ni fausse)

La valeur de vérité d'une proposition est donc Vrai (V ou 1) ou Faux (F ou 0).

Pour combiner des propositions simples et en créer de plus complexes, nous utilisons des connecteurs logiques :

• ET (conjonction), noté $\land$ : La proposition "$A \land B$" est vraie si et seulement si A est vraie ET B est vraie.

  • Exemple : "Il pleut ET il fait froid."
  • Table de vérité :

    A	B	A $\land$ B
    V	V	V
    V	F	F
    F	V	F
    F	F	F

• OU (disjonction), noté $\lor$ : La proposition "$A \lor B$" est vraie si et seulement si A est vraie OU B est vraie (ou les deux). C'est le "ou" inclusif.

  • Exemple : "Je prendrai du café OU du thé." (Je peux prendre les deux)
  • Table de vérité :

    A	B	A $\lor$ B
    V	V	V
    V	F	V
    F	V	V
    F	F	F

• NON (négation), noté $\lnot$ ou $\overline{}$ : La proposition "$\lnot A$" est vraie si et seulement si A est fausse.

  • Exemple : "NON il pleut" signifie "Il ne pleut pas."
  • Table de vérité :

    A	$\lnot$ A
    V	F
    F	V

Ces tables de vérité sont les fondations de l'évaluation de la validité de toutes les expressions logiques complexes.

Ces deux connecteurs sont absolument cruciaux en mathématiques pour exprimer des relations de cause à effet ou d'identité logique.

• Implication (si... alors...), notée $\Rightarrow$ : La proposition "$A \Rightarrow B$" (lire "si A alors B") est fausse UNIQUEMENT si A est vraie ET B est fausse. Dans tous les autres cas, elle est vraie.

  • A est l'hypothèse ou l'antécédent.
  • B est la conclusion ou le conséquent.
  • Une implication est toujours vraie si son hypothèse est fausse, quelle que soit la conclusion. C'est un point souvent contre-intuitif mais fondamental en logique.
  • Exemple : "S'il pleut ($\text{A}$), alors le sol est mouillé ($\text{B}$)."
    • S'il pleut (V) et le sol est mouillé (V) $\rightarrow$ l'implication est Vraie.
    • S'il pleut (V) et le sol n'est PAS mouillé (F) $\rightarrow$ l'implication est Fausse.
    • S'il ne pleut PAS (F) et le sol est mouillé (V) $\rightarrow$ l'implication est Vraie (le sol peut être mouillé pour d'autres raisons, comme un arrosage).
    • S'il ne pleut PAS (F) et le sol n'est PAS mouillé (F) $\rightarrow$ l'implication est Vraie.
  • Table de vérité :

    A	B	A $\Rightarrow$ B
    V	V	V
    V	F	F
    F	V	V
    F	F	V

• Équivalence (si et seulement si), notée $\Leftrightarrow$ : La proposition "$A \Leftrightarrow B$" (lire "A si et seulement si B" ou "A est équivalent à B") est vraie si A et B ont la même valeur de vérité. Elle est fausse si elles ont des valeurs de vérité différentes.

  • $A \Leftrightarrow B$ est équivalent à $(A \Rightarrow B) \land (B \Rightarrow A)$.
  • Exemple : "Un triangle est équilatéral $\Leftrightarrow$ ses trois côtés sont de même longueur."
  • Table de vérité :

    A	B	A $\Leftrightarrow$ B
    V	V	V
    V	F	F
    F	V	F
    F	F	V

L'équivalence est très importante car elle signifie que deux propositions sont logiquement interchangeables.

Les quantificateurs permettent d'exprimer des propriétés sur des ensembles d'éléments.

• Quantificateur universel (Pour tout), noté $\forall$ : Signifie "pour tout", "pour chaque", "quel que soit".

  • $\forall x \in E, P(x)$ signifie que la propriété $P(x)$ est vraie pour TOUS les éléments $x$ de l'ensemble $E$.
  • Exemple : $\forall n \in \mathbb{N}, n \ge 0$ (Pour tout entier naturel $n$, $n$ est supérieur ou égal à 0). C'est Vrai.
  • Exemple : $\forall x \in \mathbb{R}, x^2 > 0$ (Pour tout réel $x$, $x^2$ est strictement positif). C'est Faux (car $0^2 = 0$).

• Quantificateur existentiel (Il existe), noté $\exists$ : Signifie "il existe (au moins un)", "il y a".

  • $\exists x \in E, P(x)$ signifie qu'il existe AU MOINS UN élément $x$ de l'ensemble $E$ pour lequel la propriété $P(x)$ est vraie.
  • Exemple : $\exists x \in \mathbb{R}, x^2 = 4$ (Il existe un réel $x$ tel que $x^2 = 4$). C'est Vrai (par exemple $x=2$ ou $x=-2$).
  • Exemple : $\exists n \in \mathbb{N}, n < 0$ (Il existe un entier naturel $n$ tel que $n$ est négatif). C'est Faux.

• Négation des propositions quantifiées : C'est une erreur fréquente.

  • La négation de "$\forall x \in E, P(x)$" est "$\exists x \in E, \lnot P(x)$".
    • Exemple : Négation de "Tous les élèves ont réussi" est "Il existe au moins un élève qui n'a pas réussi".
  • La négation de "$\exists x \in E, P(x)$" est "$\forall x \in E, \lnot P(x)$".
    • Exemple : Négation de "Il existe un chat noir" est "Tous les chats ne sont pas noirs" (ou "Aucun chat n'est noir").

• Ordre des quantificateurs : L'ordre des quantificateurs est CRUCIAL et change le sens de la proposition.

  • $\forall x, \exists y, P(x,y)$ : Pour chaque $x$, il existe un $y$ (qui peut dépendre de $x$) tel que $P(x,y)$ est vraie.
    • Exemple : $\forall n \in \mathbb{N}, \exists m \in \mathbb{N}, m > n$ (Pour tout entier $n$, il existe un entier $m$ qui lui est strictement supérieur). C'est Vrai (par exemple, $m=n+1$).
  • $\exists y, \forall x, P(x,y)$ : Il existe un $y$ (fixe pour tous les $x$) tel que pour chaque $x$, $P(x,y)$ est vraie.
    • Exemple : $\exists m \in \mathbb{N}, \forall n \in \mathbb{N}, m > n$ (Il existe un entier $m$ qui est strictement supérieur à TOUS les entiers $n$). C'est Faux.

Le raisonnement déductif est la forme la plus courante de démonstration en mathématiques. Il consiste à partir de prémisses (définitions, axiomes, théorèmes déjà établis) considérées comme vraies pour en tirer une conclusion spécifique et nécessairement vraie.

• Principe : Si les prémisses sont vraies, alors la conclusion DOIT être vraie.
• Structure :
  1. Prémisse 1 (règle générale)
  2. Prémisse 2 (cas spécifique)
  3. Conclusion (application de la règle au cas spécifique)
• Exemples en mathématiques :
  • Prémisse 1 : Tous les multiples de 2 sont des nombres pairs.
  • Prémisse 2 : 10 est un multiple de 2.
  • Conclusion : Donc, 10 est un nombre pair.
  • Autre exemple :
    • Prémisse 1 : Si un triangle est rectangle, alors il vérifie le théorème de Pythagore.
    • Prémisse 2 : Le triangle ABC est rectangle en A.
    • Conclusion : Donc, $AB^2 + AC^2 = BC^2$.

Le raisonnement déductif est la base de la construction des théories mathématiques. Chaque étape doit être justifiée par une règle logique ou un fait établi.

Ce type de raisonnement est utilisé lorsque l'on ne peut pas traiter une situation de manière globale, mais qu'elle peut être découpée en un nombre fini de cas distincts et exhaustifs.

• Principe : Pour prouver une propriété $P$, on montre que cette propriété est vraie dans chacun des cas possibles qui couvrent toutes les situations.
• Étapes :
  1. Identifier tous les cas possibles et mutuellement exclusifs (ou du moins dont l'union couvre toutes les possibilités) pour la situation étudiée.
  2. Démontrer la propriété pour le Cas 1.
  3. Démontrer la propriété pour le Cas 2.
  4. ...
  5. Démontrer la propriété pour le Cas $n$.
  6. Conclure que la propriété est vraie dans tous les cas, donc globalement.
• Exemples d'application :
  • Pour prouver une propriété sur un entier $n$, on peut distinguer :
    • Cas 1 : $n$ est pair.
    • Cas 2 : $n$ est impair.
  • Pour prouver une propriété sur la valeur absolue $|x|$ :
    • Cas 1 : $x \ge 0$, alors $|x|=x$.
    • Cas 2 : $x < 0$, alors $|x|=-x$.
  • Exemple : Démontrer que pour tout entier $n$, $n(n+1)$ est pair.
    • Cas 1 : $n$ est pair. Alors $n=2k$ pour un entier $k$. Donc $n(n+1) = 2k(2k+1)$, qui est un multiple de 2, donc pair.
    • Cas 2 : $n$ est impair. Alors $n=2k+1$ pour un entier $k$. Donc $n+1 = 2k+2 = 2(k+1)$. Donc $n(n+1) = (2k+1)2(k+1)$, qui est un multiple de 2, donc pair.
    • Conclusion : Dans tous les cas, $n(n+1)$ est pair.

Il est crucial de s'assurer que les cas sont bien exhaustifs (ils couvrent toutes les possibilités) et distincts (pour éviter les redondances, même si ce n'est pas une obligation stricte).

Ce raisonnement est souvent utilisé pour les problèmes d'existence et d'unicité, ou pour la construction d'objets mathématiques. Il se déroule en deux phases principales.

• Phase d'Analyse (Recherche) :
  • On suppose que le problème a une solution et qu'elle existe.
  • On travaille "à rebours" à partir de cette solution supposée pour en déduire les propriétés qu'elle devrait nécessairement avoir.
  • Cette phase permet d'identifier les caractéristiques de la solution ou la méthode pour la construire. Elle aboutit à une "solution candidate" ou à une condition nécessaire.
• Phase de Synthèse (Vérification) :
  • On prend la solution candidate trouvée lors de la phase d'analyse.
  • On vérifie que cette solution candidate satisfait bien les conditions initiales du problème.
  • On prouve l'existence et l'unicité de la solution.
• Utilité pour les problèmes d'existence et d'unicité : L'analyse montre qu'il ne peut y avoir qu'une seule solution (unicité), et la synthèse montre que cette solution existe réellement.
• Exemples de construction :

  • Problème : Trouver une fonction $f$ telle que $f(x) + f(-x) = 2x$ pour tout $x \in \mathbb{R}$.

    • Analyse :
      1. Supposons qu'une telle fonction $f$ existe.
      2. On a $f(x) + f(-x) = 2x$ (Équation 1)
      3. Remplaçons $x$ par $-x$ dans l'Équation 1 : $f(-x) + f(x) = 2(-x) = -2x$ (Équation 2)
      4. Oh, on obtient la même équation ! Cela ne nous aide pas directement pour trouver $f$.
      5. Tentons une autre approche : On cherche $f(x)$. Si on a $f(x)+f(-x)=2x$, et si on avait une autre relation pour $f(x)$ et $f(-x)$, on pourrait résoudre un système.
      6. Considérons une décomposition $f(x) = P(x) + I(x)$ où $P$ est paire ($P(x)=P(-x)$) et $I$ est impaire ($I(x)=-I(-x)$).
      7. Alors $f(x)+f(-x) = (P(x)+I(x)) + (P(-x)+I(-x)) = (P(x)+I(x)) + (P(x)-I(x)) = 2P(x)$.
      8. Donc $2P(x) = 2x \Rightarrow P(x) = x$.
      9. Cela signifie que la partie paire de $f$ doit être $x$. Mais $x$ n'est pas une fonction paire ($(-x) = -x \ne x$). Ce chemin ne semble pas aboutir directement.
      10. Reprenons l'idée du système. On a $f(x) + f(-x) = 2x$.
      11. Si on suppose que $f$ est linéaire, $f(x)=ax+b$. Alors $ax+b + a(-x)+b = ax+b-ax+b = 2b$. Donc $2b=2x$, ce qui est impossible car $2b$ est une constante et $2x$ ne l'est pas.
      12. Re-reprenons : On cherche $f(x)$. On a $f(x) + f(-x) = 2x$.
      13. Si on dérive (si $f$ est dérivable) : $f'(x) - f'(-x) = 2$.
      14. Si $f(x) = ax^2+bx+c$, alors $ax^2+bx+c + a(-x)^2+b(-x)+c = ax^2+bx+c+ax^2-bx+c = 2ax^2+2c$.
      15. Donc $2ax^2+2c=2x$. Impossible car $2ax^2$ n'est pas $2x$ sauf si $a=0$. Si $a=0$, on a $2c=2x$, impossible.
      16. Insight : Et si $f(x)=x+g(x)$ où $g$ est une fonction impaire ?
      17. Alors $(x+g(x)) + (-x+g(-x)) = x+g(x)-x-g(x) = 0$. On veut $2x$.
      18. Alternative : On cherche $f(x)$. On a $f(x)+f(-x)=2x$.
      19. On peut chercher $f(x)$ sous la forme $ax+b$. On a vu que ça ne marche pas.
      20. On sait que $f(x) = P(x) + I(x)$ où $P(x) = \frac{f(x)+f(-x)}{2}$ et $I(x) = \frac{f(x)-f(-x)}{2}$.
      21. D'après l'énoncé, $f(x)+f(-x) = 2x$.
      22. Donc $P(x) = \frac{2x}{2} = x$.
      23. Donc $f(x) = x + I(x)$, où $I(x)$ est une fonction impaire quelconque.
      24. La phase d'analyse nous dit que si une solution existe, elle doit être de la forme $f(x) = x + I(x)$ où $I$ est impaire.
    • Synthèse :
      1. Soit $f(x) = x + I(x)$ où $I$ est une fonction impaire quelconque (par exemple $I(x)=0$, ou $I(x)=x^3$).
      2. Vérifions si cette forme satisfait la condition : $f(x) + f(-x) = (x + I(x)) + (-x + I(-x))$ Comme $I$ est impaire, $I(-x) = -I(x)$. $f(x) + f(-x) = x + I(x) - x - I(x) = 0$.
      3. Ah, il y a une erreur dans le raisonnement d'analyse ou dans l'application. Reprenons l'analyse à partir de $P(x) = x$. $f(x) = P(x) + I(x)$ où $P(x) = x$. Donc $f(x) = x + I(x)$ pour une fonction impaire $I$. Alors $f(-x) = -x + I(-x) = -x - I(x)$. $f(x) + f(-x) = (x + I(x)) + (-x - I(x)) = 0$.
      4. On voulait $f(x)+f(-x)=2x$. Il y a une contradiction. Cela signifie qu'il n'existe pas de fonction $f$ telle que $f(x)+f(-x)=2x$ pour tout $x$.
      5. Correction de la compréhension de l'énoncé de l'exemple : Si on avait $f(x) = x + C$ (constante), alors $f(x)+f(-x) = (x+C)+(-x+C) = 2C$. Donc $2C=2x$, impossible.
      6. Moralité : Le raisonnement par analyse-synthèse peut aussi conclure à l'inexistence d'une solution si la synthèse échoue ou révèle une contradiction.

  • Exemple plus simple : Résoudre l'équation $x+1 = \sqrt{x+3}$.

    • Analyse :
      1. Supposons qu'il existe une solution $x$.
      2. Pour que $\sqrt{x+3}$ soit défini, il faut $x+3 \ge 0 \Rightarrow x \ge -3$.
      3. Pour que $x+1 = \sqrt{x+3}$ ait un sens, il faut $x+1 \ge 0 \Rightarrow x \ge -1$.
      4. Élevons au carré les deux membres : $(x+1)^2 = x+3$.
      5. $x^2+2x+1 = x+3$.
      6. $x^2+x-2 = 0$.
      7. Calcul du discriminant $\Delta = 1^2 - 4(1)(-2) = 1+8=9$.
      8. Les solutions de cette équation sont $x = \frac{-1 \pm \sqrt{9}}{2} = \frac{-1 \pm 3}{2}$.
      9. Donc $x_1 = \frac{-1+3}{2} = 1$ et $x_2 = \frac{-1-3}{2} = -2$.
      10. Ces solutions sont des candidats.
    • Synthèse :
      1. Vérifions $x_1=1$ : $1 \ge -1$ (condition respectée). $1+1 = 2$. $\sqrt{1+3} = \sqrt{4} = 2$. Donc $x=1$ est solution.
      2. Vérifions $x_2=-2$ : $-2 < -1$ (condition $x \ge -1$ NON respectée). Donc $x=-2$ n'est pas solution.
      3. Conclusion : La seule solution de l'équation est $x=1$.

Le raisonnement par contraposition est basé sur une équivalence logique fondamentale : une implication $A \Rightarrow B$ est logiquement équivalente à sa contraposée $\lnot B \Rightarrow \lnot A$.

• Définition de la contraposée : La contraposée de "$A \Rightarrow B$" est "$\lnot B \Rightarrow \lnot A$".
• Équivalence logique : $(A \Rightarrow B) \Leftrightarrow (\lnot B \Rightarrow \lnot A)$.
  • On peut le vérifier avec une table de vérité :

    A	B	$\lnot$ A	$\lnot$ B	A $\Rightarrow$ B	$\lnot$ B $\Rightarrow$ $\lnot$ A
    V	V	F	F	V	V
    V	F	F	V	F	F
    F	V	V	F	V	V
    F	F	V	V	V	V
    Les deux colonnes sont identiques, prouvant l'équivalence.

• Quand l'utiliser ? Ce raisonnement est très puissant lorsque la négation de la conclusion ($\lnot B$) rend les calculs ou la logique plus simple à manipuler que l'hypothèse $A$.
• Exemples de démonstrations :
  • Propriété à prouver : Si $n^2$ est pair, alors $n$ est pair (où $n$ est un entier naturel).
    • $A : n^2$ est pair.
    • $B : n$ est pair.
    • La démonstration directe serait un peu compliquée.
    • Utilisons la contraposée : $\lnot B \Rightarrow \lnot A$.
    • $\lnot B : n$ est impair.
    • $\lnot A : n^2$ est impair.
    • La contraposée devient : "Si $n$ est impair, alors $n^2$ est impair."
    • Démonstration de la contraposée :
      1. Supposons $n$ est impair.
      2. Alors $n$ peut s'écrire sous la forme $2k+1$ pour un certain entier $k$.
      3. Calculons $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$.
      4. Puisque $2k^2+2k$ est un entier, $n^2$ est de la forme $2K+1$, donc $n^2$ est impair.
    • Nous avons prouvé la contraposée. Par équivalence, la propriété originale est vraie.

Le raisonnement par l'absurde (ou reductio ad absurdum) est une technique de démonstration indirecte très élégante. Il repose sur le principe du tiers exclu : une proposition est soit vraie, soit fausse.

• Principe : Pour prouver qu'une proposition $P$ est vraie, on suppose que sa négation $\lnot P$ est vraie. Si cette supposition mène à une contradiction logique (un résultat absurde, comme $0=1$, ou une affirmation qui contredit une prémisse ou un théorème connu), alors la supposition $\lnot P$ doit être fausse. Par conséquent, $P$ doit être vraie.
• Étapes :
  1. Pour prouver $P$, on suppose $\lnot P$.
  2. On développe une chaîne de déductions logiques à partir de $\lnot P$ et des hypothèses initiales du problème.
  3. On arrive à une contradiction (par exemple, $Q \land \lnot Q$, ou $Vrai = Faux$).
  4. On conclut que la supposition $\lnot P$ est fausse.
  5. Donc, $P$ est vraie.
• Exemples classiques :
  • L'irrationalité de $\sqrt{2}$ :
    • Propriété à prouver ($P$) : $\sqrt{2}$ est irrationnel.
    • Supposition par l'absurde ($\lnot P$) : Supposons que $\sqrt{2}$ est rationnel.
    • Déduction :
      1. Si $\sqrt{2}$ est rationnel, alors il peut s'écrire sous la forme $\frac{p}{q}$ où $p$ et $q$ sont des entiers naturels non nuls, et la fraction $\frac{p}{q}$ est irréductible (c'est-à-dire que $p$ et $q$ n'ont pas de facteurs premiers en commun, ils sont premiers entre eux).
      2. $\sqrt{2} = \frac{p}{q} \Rightarrow 2 = \frac{p^2}{q^2} \Rightarrow 2q^2 = p^2$.
      3. Cette dernière égalité implique que $p^2$ est un nombre pair.
      4. Si $p^2$ est pair, alors $p$ est pair (démontré par contraposition précédemment).
      5. Puisque $p$ est pair, on peut écrire $p = 2k$ pour un certain entier $k$.
      6. Substituons $p=2k$ dans l'équation $2q^2=p^2$ : $2q^2 = (2k)^2 = 4k^2$.
      7. En divisant par 2, on obtient $q^2 = 2k^2$.
      8. Cette égalité implique que $q^2$ est un nombre pair.
      9. Si $q^2$ est pair, alors $q$ est pair (encore par contraposition).
      10. Nous avons donc déduit que $p$ est pair ET $q$ est pair.
    • Contradiction : Si $p$ et $q$ sont tous les deux pairs, alors ils ont 2 comme facteur commun. Ceci contredit notre hypothèse initiale que la fraction $\frac{p}{q}$ est irréductible.
    • Conclusion : La supposition que $\sqrt{2}$ est rationnel mène à une contradiction. Par conséquent, cette supposition est fausse, et $\sqrt{2}$ est bien irrationnel.

Le raisonnement par l'absurde est particulièrement efficace pour prouver l'inexistence de quelque chose ou l'impossibilité d'une situation.

Le raisonnement par récurrence est une méthode pour prouver qu'une propriété $P(n)$ est vraie pour tous les entiers naturels $n$ à partir d'un certain rang (souvent $n_0=0$ ou $n_0=1$).

• Utilité : Il est utilisé pour les suites, les sommes, les inégalités, les propriétés de divisibilité, etc., où la propriété dépend d'un index entier.

• Analogie de la chaîne de dominos :

  1. Si vous poussez le premier domino (étape d'initialisation).
  2. Et si chaque domino qui tombe fait tomber le suivant (étape d'hérédité).
  3. Alors tous les dominos tomberont (conclusion). La propriété $P(n)$ est comme le fait que le $n$-ième domino tombe.

• Structure du raisonnement : Pour prouver que $P(n)$ est vraie pour tout $n \ge n_0$ :

  1. Initialisation : Montrer que $P(n_0)$ est vraie.
  2. Hérédité : Supposer que $P(k)$ est vraie pour un entier $k \ge n_0$ (c'est l'hypothèse de récurrence), puis montrer que $P(k+1)$ est vraie.
  3. Conclusion : Par le principe de récurrence, $P(n)$ est vraie pour tout $n \ge n_0$.

Reprenons les étapes avec plus de détails et des conseils.

1. Initialisation ($P(n_0)$) :

   • Il s'agit de vérifier que la propriété est vraie pour le premier terme de la séquence, $n_0$. C'est souvent $n=0$ ou $n=1$.
   • C'est une simple vérification directe. Si l'initialisation échoue, la propriété est fausse ou le rang de départ est incorrect.

2. Hérédité ($P(k) \Rightarrow P(k+1)$) :

   • Hypothèse de récurrence : On suppose que la propriété $P(k)$ est vraie pour un entier $k$ quelconque fixé, $k \ge n_0$. On ne suppose PAS que $P(k)$ est vraie pour TOUS les $k$.
   • But : Montrer qu'alors $P(k+1)$ est vraie. C'est l'étape la plus difficile et le cœur de la démonstration.
   • Il faut utiliser l'hypothèse de récurrence $P(k)$ pour prouver $P(k+1)$. Souvent, cela implique d'exprimer le $(k+1)$-ième terme en fonction du $k$-ième terme.

3. Conclusion :

   • Une fois l'initialisation et l'hérédité prouvées, on peut affirmer : "Par le principe de récurrence, la propriété $P(n)$ est vraie pour tout entier naturel $n \ge n_0$."

• Erreurs courantes à éviter :

  • Oublier l'initialisation (le premier domino ne tombe jamais).
  • Ne pas utiliser l'hypothèse de récurrence dans la phase d'hérédité (vous ne montrez pas que le $k$-ième domino fait tomber le $(k+1)$-ième).
  • Confondre $P(k)$ et $P(k+1)$ ou ne pas clairement distinguer ce que l'on suppose de ce que l'on veut prouver.
  • Affirmer la propriété pour tous les $n$ dès le début de l'hérédité.

• Exemple : Montrer que pour tout $n \in \mathbb{N}^*$ (entiers naturels non nuls), la somme des $n$ premiers entiers est $S_n = 1+2+...+n = \frac{n(n+1)}{2}$.

  • Propriété $P(n)$ : $1+2+...+n = \frac{n(n+1)}{2}$.
  • 1. Initialisation ($n_0=1$) :
    • Pour $n=1$, $S_1 = 1$.
    • La formule donne $\frac{1(1+1)}{2} = \frac{1 \times 2}{2} = 1$.
    • Donc $P(1)$ est vraie.
  • 2. Hérédité :
    • Supposons que $P(k)$ est vraie pour un entier $k \ge 1$. C'est-à-dire, on suppose $1+2+...+k = \frac{k(k+1)}{2}$. (Hypothèse de récurrence)
    • Montrons que $P(k+1)$ est vraie, c'est-à-dire que $1+2+...+(k+1) = \frac{(k+1)(k+2)}{2}$.
    • Partons du membre de gauche de $P(k+1)$ : $1+2+...+k+(k+1) = (1+2+...+k) + (k+1)$
    • En utilisant l'hypothèse de récurrence : $= \frac{k(k+1)}{2} + (k+1)$ $= (k+1) \left( \frac{k}{2} + 1 \right)$ $= (k+1) \left( \frac{k+2}{2} \right)$ $= \frac{(k+1)(k+2)}{2}$
    • Nous avons bien montré que $1+2+...+(k+1) = \frac{(k+1)(k+2)}{2}$. Donc $P(k+1)$ est vraie.
  • 3. Conclusion : Puisque $P(1)$ est vraie et que $P(k) \Rightarrow P(k+1)$ est vraie, par le principe de récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}^*$.

Le principe de récurrence peut être adapté pour des situations légèrement différentes.

• Récurrence forte :

  • L'hypothèse de récurrence n'est plus seulement $P(k)$, mais "pour tout $j$ tel que $n_0 \le j \le k$, la propriété $P(j)$ est vraie".
  • On utilise cette forme lorsque la preuve de $P(k+1)$ nécessite la connaissance de plusieurs termes précédents, pas seulement $P(k)$.
  • Exemple : Définition de suites par récurrence où $u_{n+1}$ dépend de $u_n$ et $u_{n-1}$.

• Récurrence à plusieurs pas :

  • Similaire à la récurrence forte, mais on prouve $P(k+p)$ à partir de $P(k)$. L'initialisation doit alors être faite pour $p$ premiers termes.

• Démonstration de formules :

  • Sommes : Comme l'exemple précédent ($1+2+...+n$).
  • Produits : Par exemple, $P(n): \prod_{i=1}^n (1 - \frac{1}{i+1}) = \frac{1}{n+1}$.
  • Inégalités : Par exemple, $P(n): 2^n > n$ pour $n \ge 1$.

• Étude de suites numériques :

  • Prouver qu'une suite est majorée/minorée, croissante/décroissante.
  • Exemple : Soit $(u_n)$ une suite définie par $u_0=0$ et $u_{n+1} = \sqrt{u_n+2}$. Montrer que $0 \le u_n \le 2$ pour tout $n$.
    • Initialisation : $u_0=0$, donc $0 \le u_0 \le 2$ est vraie.
    • Hérédité : Supposons $0 \le u_k \le 2$ pour un $k \ge 0$.
      • Alors $0+2 \le u_k+2 \le 2+2$, donc $2 \le u_k+2 \le 4$.
      • En prenant la racine carrée (la fonction racine est croissante sur $[0, +\infty[$) : $\sqrt{2} \le \sqrt{u_k+2} \le \sqrt{4}$.
      • Donc $\sqrt{2} \le u_{k+1} \le 2$.
      • Puisque $\sqrt{2} \ge 0$, on a bien $0 \le u_{k+1} \le 2$. L'hérédité est prouvée.
    • Conclusion : Par récurrence, pour tout $n \in \mathbb{N}$, $0 \le u_n \le 2$.

• Confondre implication et réciproque :

  • L'implication est $A \Rightarrow B$.
  • La réciproque est $B \Rightarrow A$.
  • Ces deux propositions ne sont PAS logiquement équivalentes. La vérité de l'une n'entraîne pas la vérité de l'autre.
  • Exemple : "S'il pleut ($\text{A}$), alors le sol est mouillé ($\text{B}$)." (Vraie, en général)
  • Réciproque : "Si le sol est mouillé ($\text{B}$), alors il pleut ($\text{A}$)." (Fausse, le sol peut être mouillé par un arrosage).
  • Piège : Affirmer la réciproque comme si elle était vraie, alors qu'elle ne l'est pas.

• Confondre implication et contraposée :

  • L'implication $A \Rightarrow B$ et sa contraposée $\lnot B \Rightarrow \lnot A$ SONT logiquement équivalentes.
  • C'est une erreur de croire qu'elles ne le sont pas, ou de penser que la contraposée est la réciproque.

• Affirmation du conséquent :

  • C'est un sophisme courant. Partir de $A \Rightarrow B$ et de $B$ pour conclure $A$.
  • Exemple : "Si j'ai la grippe ($\text{A}$), alors j'ai de la fièvre ($\text{B}$)." (Vrai)
  • "J'ai de la fièvre ($\text{B}$)."
  • Fausse conclusion : "Donc j'ai la grippe ($\text{A}$)." (On peut avoir de la fièvre pour d'autres raisons).

• Négation incorrecte de propositions :

  • Nier "ET" par "OU" et vice-versa (lois de De Morgan).
    • $\lnot (A \land B) \Leftrightarrow (\lnot A \lor \lnot B)$
    • $\lnot (A \lor B) \Leftrightarrow (\lnot A \land \lnot B)$
  • Nier les quantificateurs (vu précédemment).
    • $\lnot (\forall x, P(x)) \Leftrightarrow (\exists x, \lnot P(x))$
    • $\lnot (\exists x, P(x)) \Leftrightarrow (\forall x, \lnot P(x))$
  • Ces erreurs peuvent invalider toute une démonstration.

La rigueur est la qualité la plus importante en mathématiques. Une démonstration n'est valide que si chaque étape est justifiée de manière irréfutable.

• Importance de la définition des termes : Avant de commencer une démonstration, assurez-vous que tous les termes et symboles utilisés sont clairement définis. Que signifie "pair" ? "Premier" ? "Convergent" ?
• Clarté des étapes de la démonstration :
  • Chaque transition d'une étape à l'autre doit être logique et explicite.
  • Utilisez des mots de liaison clairs ("donc", "ainsi", "par conséquent", "on en déduit", "car").
  • Évitez les "sauts logiques" où une étape est implicitement supposée.
• Justification de chaque affirmation :
  • Toute affirmation doit être une définition, un axiome, une hypothèse du problème, ou un théorème/lemme/propriété préalablement établi(e) et prouvé(e).
  • Ne laissez aucune affirmation "en l'air".
• Exemples de démonstrations fallacieuses :
  • Preuve que $1=0$ :
    1. Soient $a$ et $b$ deux nombres réels tels que $a=b$.
    2. Multiplions par $a$ : $a^2 = ab$.
    3. Soustraire $b^2$ : $a^2 - b^2 = ab - b^2$.
    4. Factoriser : $(a-b)(a+b) = b(a-b)$.
    5. Diviser par $(a-b)$ : $a+b = b$.
    6. Puisque $a=b$, on a $b+b=b$, soit $2b=b$.
    7. Si $b \ne 0$, on peut diviser par $b$ et obtenir $2=1$.
    8. Si on part de $a=1, b=1$, alors $2=1$.
    • Où est l'erreur ? L'erreur est à l'étape 5. Pour diviser par $(a-b)$, il faut que $a-b \ne 0$. Or, si $a=b$, alors $a-b=0$. La division par zéro est une opération indéfinie et invalide le raisonnement.

La pratique régulière de la démonstration, l'analyse critique des arguments et la relecture attentive de vos propres preuves sont les meilleures façons de développer une rigueur mathématique solide.