Éléments de logique et raisonnement par récurrence

Résumé en cinq points

1Propositions et connecteurs logiques

1.1Proposition

1.2Négation

1.3Connecteurs « et » et « ou »

Le « ou » des mathématiques est inclusif : il n'exclut pas le cas où les deux sont vraies.

Ces deux connecteurs correspondent aux opérations sur les ensembles, intersection pour le « et » et réunion pour le « ou », et aux opérations sur les événements en probabilités.

2La proposition conditionnelle

2.1Implication

En particulier, une implication dont l'hypothèse est fausse est vraie, ce qui surprend au début mais ne pose jamais de problème en pratique.

2.2Réciproque, contraposée, négation

Trois énoncés se construisent à partir de $P \Rightarrow Q$ et il ne faut jamais les confondre.

2.3Équivalence

Pour démontrer une équivalence, le plus sûr est de démontrer les deux implications séparément.

2.4Quantifications implicites

Beaucoup d'énoncés conditionnels cachent un « pour tout ».

Repérer cette quantification cachée est indispensable pour savoir nier correctement.

3Quantificateurs

3.1Les deux quantificateurs

Pour la démontrer, on écrit « soit $x$ un élément de $E$ » et on démontre $P(x)$ sans jamais utiliser de propriété particulière de $x$.

Pour la démontrer, on exhibe un élément précis et on vérifie qu'il convient, ou on invoque un théorème d'existence.

3.2Négation d'une phrase quantifiée

La règle est mécanique : on échange chaque $\forall$ en $\exists$ et chaque $\exists$ en $\forall$, dans l'ordre où ils apparaissent, puis on nie la propriété finale.

Autrement dit, on réfute une proposition universelle par un contre-exemple unique.

3.3L'ordre des quantificateurs compte

On peut permuter deux quantificateurs de même nature, jamais un $\forall$ et un $\exists$.

3.4Règle d'écriture

Le programme exclut explicitement l'emploi des quantificateurs comme abréviations. On n'écrit pas « la suite est croissante $\forall n$ ». On écrit soit une phrase entièrement en français, soit une formule entièrement symbolique.

4Les types de raisonnement

4.1Raisonnement direct

On part des hypothèses et on enchaîne des implications vraies jusqu'à la conclusion. C'est le mode par défaut.

4.2Raisonnement par contraposée

Pour démontrer $P \Rightarrow Q$, on démontre « non $Q \Rightarrow$ non $P$ ». On l'utilise quand la négation de la conclusion est plus facile à manipuler que l'hypothèse.

4.3Raisonnement par l'absurde

Pour démontrer une proposition $P$, on suppose « non $P$ » et on aboutit à une contradiction.

4.4Disjonction des cas

On découpe la situation en cas couvrant toutes les possibilités et on démontre la conclusion dans chaque cas. Vérifier que les cas sont exhaustifs fait partie de la démonstration. C'est l'outil naturel pour les valeurs absolues et la partie entière.

4.5Contre-exemple

Un seul contre-exemple réfute une proposition universelle, et il doit être explicité complètement. À l'inverse un exemple ne démontre jamais une proposition universelle.

4.6Analyse-synthèse

L'introduction du programme cite ce mode de raisonnement. Pour déterminer tous les objets vérifiant une propriété :

• analyse : on suppose qu'un objet convient et on en déduit sa forme obligatoire, ce qui donne des candidats ;
• synthèse : on vérifie ensuite lesquels conviennent vraiment.

5Le raisonnement par récurrence

5.1Principe

Une rédaction de récurrence comporte trois parties nommées :

• Initialisation : on vérifie $P(n_0)$, en calculant explicitement les deux membres.
• Hérédité : on fixe un entier $n \geqslant n_0$, on suppose $P(n)$ vraie (c'est l'hypothèse de récurrence), et on démontre $P(n+1)$.
• Conclusion : on invoque le principe de récurrence et on énonce le résultat.

5.2Exemple

5.3Deux variantes utiles

5.4Erreurs classiques

6Notations somme et produit

6.1Écriture

Deux règles servent en permanence :

• la linéarité : $\sum (\lambda u_i + v_i) = \lambda \sum u_i + \sum v_i$ ;
• le changement d'indice, qui décale ou retourne l'indice à condition de changer les bornes.

6.2Sommes à connaître

6.3Télescopage

6.4Factorielle

Cette notation prépare le chapitre des coefficients binomiaux.

6.5Lien avec l'informatique

Une somme se traduit directement par une boucle. En pseudo-code, on initialise une variable $s$ à 0, puis pour chaque $k$ allant de 1 à $n$ on remplace $s$ par $s + u(k)$, et on renvoie $s$.

def somme(u, n):
    s = 0
    for k in range(1, n + 1):
        s = s + u(k)
    return s

La bibliothèque numpy fournit np.sum pour sommer les coefficients d'un tableau.

Méthodes

Ce qu'il faut savoir refaire en khôlle

1. Donner la réciproque, la contraposée et la négation d'un énoncé conditionnel proposé en français.
2. Nier une phrase à deux ou trois quantificateurs et interpréter la négation obtenue.
3. Expliquer avec un exemple pourquoi « $\forall x\ \exists y$ » et « $\exists y\ \forall x$ » n'ont pas le même sens.
4. Démontrer par contraposée que si $n^2$ est pair alors $n$ est pair.
5. Démontrer par l'absurde que $\sqrt{2}$ est irrationnel.
6. Rédiger une récurrence simple complète, en nommant les trois étapes.
7. Mettre en place une récurrence double sur une suite définie par $u_{n+2} = a\,u_{n+1} + b\,u_n$.
8. Calculer une somme géométrique, une somme d'entiers, une somme télescopique, en traitant les cas particuliers.

Les résultats à connaître

• Lois de De Morgan logiques. non(P et Q) équivaut à (non P ou non Q), non(P ou Q) équivaut à (non P et non Q). Exigibles, justification par table de vérité.
• Une implication P ⇒ Q équivaut à sa contraposée non Q ⇒ non P. Sa réciproque Q ⇒ P est indépendante. Sa négation est (P et non Q). Exigibles, table de vérité ou lecture des cas.
• Condition nécessaire et condition suffisante. Dans P ⇒ Q, P est suffisante pour Q, Q est nécessaire pour P. Vocabulaire exigible.
• Négation d'une phrase quantifiée. On échange ∀ et ∃ dans l'ordre d'apparition, puis on nie la propriété finale. Exigible, à appliquer sans hésiter.
• Un contre-exemple réfute une proposition universelle. Un exemple ne démontre jamais une proposition universelle. Exigible.
• Principe de récurrence simple, double, forte. Admis, tout exposé théorique est exclu par le programme. La rédaction en trois étapes nommées est exigible.
• Somme des entiers, Σ de k = 1 à n de k = n(n + 1)/2. Exigible avec démonstration par récurrence.
• Somme des carrés, Σ de k = 1 à n de k² = n(n + 1)(2n + 1)/6. Exigible avec démonstration par récurrence.
• Somme géométrique, pour q ≠ 1, Σ de k = 0 à n de qᵏ = (1 − qⁿ⁺¹)/(1 − q), et n + 1 si q = 1. Exigible avec démonstration.
• Télescopage, Σ de k = p à n de (a₍ₖ₊₁₎ − aₖ) = a₍ₙ₊₁₎ − aₚ. Exigible avec démonstration par récurrence ou par écriture des termes.
• Linéarité de la somme et changement d'indice. Exigibles, ce sont des règles de calcul.
• Factorielle, 0! = 1 et (n + 1)! = (n + 1) × n!. Définition exigible.
• Hors programme en ECG, à signaler si un exercice les demande. Toute axiomatique de N, la logique formelle, l'arithmétique (divisibilité comme théorie, PGCD, nombres premiers). Seule la parité d'un entier, vue au lycée, est utilisée.

Clés de démonstration

Contraposée équivalente à l'implication. Dans une table à quatre lignes, P ⇒ Q est fausse seulement pour (P vraie, Q fausse), et non Q ⇒ non P est fausse seulement pour (non Q vraie, non P fausse), qui est la même ligne. Astuce, une implication n'a qu'un seul cas de fausseté, il suffit de le comparer.

Somme des entiers. Initialisation à n = 1. Hérédité, on ajoute n + 1 à n(n + 1)/2 et on factorise par (n + 1). Astuce, factoriser avant de développer, le facteur (n + 1) est toujours là.

Somme des carrés. Hérédité, n(n + 1)(2n + 1)/6 + (n + 1)² = (n + 1)(2n² + n + 6n + 6)/6 = (n + 1)(n + 2)(2n + 3)/6. Astuce, on factorise par (n + 1), puis on vérifie que 2n² + 7n + 6 = (n + 2)(2n + 3) en développant le membre de droite.

Somme géométrique. On note S la somme, on calcule qS, et on soustrait, qS − S = qⁿ⁺¹ − 1. Astuce, la multiplication par q décale tous les termes d'un rang, tout s'annule sauf les deux extrémités. On divise par q − 1, ce qui impose q ≠ 1.

Télescopage. On écrit les termes, (a₍ₚ₊₁₎ − aₚ) + (a₍ₚ₊₂₎ − a₍ₚ₊₁₎) + … + (a₍ₙ₊₁₎ − aₙ). Chaque a intermédiaire apparaît une fois avec un plus et une fois avec un moins. Astuce, la rédaction rigoureuse est une récurrence sur n, l'écriture avec des points de suspension sert d'explication.

Parité. Si n est impair alors n² est impair, car (2k + 1)² = 2(2k² + 2k) + 1. Astuce, c'est la contraposée de « n² pair ⇒ n pair », et c'est le lemme qui sert dans l'irrationalité de √2.

Exemples et contre-exemples à connaître

1. « ∀x ∈ R, ∃y ∈ R, y > x » est vraie avec y = x + 1, alors que « ∃y ∈ R, ∀x ∈ R, y > x » est fausse. On ne permute jamais un ∀ et un ∃.
2. « Si 2 + 2 = 5 alors 7 est pair » est une implication vraie. Une hypothèse fausse rend l'implication vraie, ce qui déroute au début.
3. « x > 2 ⇒ x² > 4 » est vraie, sa réciproque est fausse, x = −3 le montre. Être supérieur à 2 est suffisant pour avoir un carré supérieur à 4, pas nécessaire.
4. La propriété « n = n + 1 » est héréditaire et fausse pour tout n. Sans initialisation, une récurrence ne démontre rien.
5. « 2ⁿ ≥ n² » est fausse pour n = 3 et vraie pour n = 0, 1, 2 puis pour tout n ≥ 4. Le rang initial d'une récurrence n'est pas toujours 0 ou 1.
6. La suite de terme général (−1)ⁿ est bornée et ne converge pas. Un seul contre-exemple réfute « toute suite bornée converge ».
7. Le « ou » mathématique est inclusif. « x ≥ 0 ou x ≤ 0 » est vraie pour tout réel, y compris pour x = 0 où les deux sont vraies.
8. La somme Σ de k = 3 à 10 de 1 vaut 8, pas 7. Le nombre de termes de p à n est n − p + 1.
9. Pour q = 1, la somme géométrique vaut n + 1 et la formule (1 − qⁿ⁺¹)/(1 − q) n'a pas de sens. Le cas q = 1 se traite à part, à chaque fois.
10. Nier « f est croissante sur R », c'est-à-dire « ∀x ∈ R, ∀y ∈ R, (x ≤ y ⇒ f(x) ≤ f(y)) », donne « ∃x ∈ R, ∃y ∈ R, x ≤ y et f(x) > f(y) ». Deux quantificateurs et une implication à nier, c'est le test de khôlle.

Techniques du chapitre

Nier une phrase quantifiée. Mini-exercice, nier « ∃M ∈ R, ∀n ∈ N, uₙ ≤ M », qui dit que la suite est majorée. Négation, « ∀M ∈ R, ∃n ∈ N, uₙ > M ». Lecture, aussi grand que soit M, un terme de la suite le dépasse.

Contraposée. Mini-exercice, montrer que si x² ≠ 4 alors x ≠ 2. Contraposée, si x = 2 alors x² = 4, ce qui est immédiat. On a démontré l'énoncé initial sans jamais manipuler x² ≠ 4.

Disjonction des cas. Mini-exercice, montrer que pour tout réel x, |x − 1| + |x + 1| ≥ 2. Si x ≥ 1, la somme vaut 2x ≥ 2. Si −1 ≤ x < 1, elle vaut (1 − x) + (x + 1) = 2. Si x < −1, elle vaut −2x > 2. Les trois cas couvrent R.

Récurrence pour une inégalité. Mini-exercice, montrer que pour tout n ∈ N, 3ⁿ ≥ 1 + 2n. Initialisation, 1 ≥ 1. Hérédité, 3ⁿ⁺¹ = 3 × 3ⁿ ≥ 3 + 6n ≥ 1 + 2(n + 1) car 6n + 3 − 2n − 3 = 4n ≥ 0. Conclusion pour tout n.

Récurrence sur une suite définie par une relation. Mini-exercice, u₀ = 3 et u₍ₙ₊₁₎ = 2uₙ − 1. Montrer uₙ = 2ⁿ⁺¹ + 1. Initialisation, 2 + 1 = 3. Hérédité, 2(2ⁿ⁺¹ + 1) − 1 = 2ⁿ⁺² + 1. Conclusion.

Changement d'indice. Mini-exercice, écrire Σ de k = 1 à n de 2ᵏ⁻¹ avec un indice partant de 0. On pose j = k − 1, qui va de 0 à n − 1, et la somme devient Σ de j = 0 à n − 1 de 2ʲ = 2ⁿ − 1.

Télescopage après décomposition. Mini-exercice, calculer Σ de k = 1 à n de 1/(k(k + 1)). Comme 1/(k(k + 1)) = 1/k − 1/(k + 1), la somme vaut 1 − 1/(n + 1) = n/(n + 1).

Somme double sur un triangle. Mini-exercice, compter les couples (i, j) d'entiers avec 1 ≤ i ≤ j ≤ n. Pour j fixé, i prend j valeurs, donc le total est Σ de j = 1 à n de j = n(n + 1)/2.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Erreurs fréquentes