Cours d'algèbre 1 PDF 2024-2025

Cours d’algèbre 1 Module 113 ó LEM-S1 Séances 1∼4 K. Abdelmoumen Copyright © 2023 U NIVERSITÉ S IDI M OHAMED B EN A BDELLAH É COLE N ORMALE S UPÉRIEURE DE F ÈS D ÉPARTEMENT DE MATHÉMATIQUES & INFORMATIQUE A NNÉE UNIVERSITAIRE : 2024-2025  Table des matières 1 Éléments de lo...

Cours d’algèbre 1 Module 113 ó LEM-S1 Séances 1∼4 K. Abdelmoumen Copyright © 2023 U NIVERSITÉ S IDI M OHAMED B EN A BDELLAH É COLE N ORMALE S UPÉRIEURE DE F ÈS D ÉPARTEMENT DE MATHÉMATIQUES & INFORMATIQUE A NNÉE UNIVERSITAIRE : 2024-2025  Table des matières 1 Éléments de logique et vocabulaire ensembliste.................... 5 1.1 Éléments de logique 5 1.1.1 Assertions............................................................ 5 1.1.2 Connecteurs logiques.................................................. 5 1.1.3 Raisonnement par l’absurde............................................. 7 1.1.4 Raisonnement par équivalences successives................................ 7 1.1.5 Raisonnement par disjonction des cas..................................... 7 1.1.6 Raisonnement par analyse-synthèse....................................... 7 1.1.7 Quantificateurs....................................................... 7 1.2 Opérations sur les ensembles 8 1.2.1 Inclusion............................................................. 8 1.2.2 Ensemble des parties d’un ensemble...................................... 9 1.2.3 Intersection et réunion.................................................. 9 1.2.4 Différence et différence symétrique....................................... 9 1.2.5 Couple, produit cartésien.............................................. 10 2 Relations binaires et applications................................... 11 2.1 Graphe - Correspondance 11 2.2 Relations binaires 11 2.2.1 Définitions et exemples................................................ 11 2.2.2 Relations d’équivalence............................................... 12 2.2.3 Relations d’ordre..................................................... 13 2.3 Raisonnement par récurrence 14 2.3.1 Principe de récurrence................................................ 14 2.3.2 Récurrence simple.................................................... 14 2.3.3 Récurrence double................................................... 15 2.3.4 Récurrence forte..................................................... 15 2.3.5 Récurrence finie..................................................... 16  1. Éléments de logique et vocabulaire ensembliste 1.1 Éléments de logique 1.1.1 Assertions Définition 1.1 — Assertion. On appelle assertion (ou proposition) un énoncé mathématique, sans variable, auquel on peut attribuer une valeur de vérité (vrai : V (ou 1) ou faux : F (ou 0)). Exemples 1.1 1. «√7 est un entier pair » est une assertion fausse. 2. « 2 est un nombre irrationnel » est une assertion vraie. 3. « 2 = 5+ » n’est pas une assertion. 4. « n est un entier pair »n’est pas une assertion car sa valeur de vérité dépend de la valeur de n. Conventions Si P est une assertion : — on écrit la plupart du temps « on a P » ou «...donc P » au lieu de « on a P est vraie » ou « donc P est vraie ». — de même on écrit « supposons P » au lieu de « supposons P vraie ». Définition 1.2 — Négation. A une assertion P, on peut associer sa négation notée non P ou ¬P et qui est définie par la table de vérité suivante : P ¬P V F F V 1.1.2 Connecteurs logiques Définition 1.3 — Connecteurs logiques. A deux assertions P et Q on peut associer leur conjonction (P et Q), leur disjonction (P ou Q), l’implication (P ⇒ Q) et l’équivalence (P ⇔ Q) qui sont définies par la table de vérité suivante : 6 Chapitre 1. Éléments de logique et vocabulaire ensembliste P Q P et Q P ou Q P⇒Q P⇔Q V V V V V V V F F V F F F V F V V F F F F F V V Remarques 1.1 1. — P ⇒ Q est toujours vraie sauf dans le cas où P est vraie et Q est fausse. — Si P est fausse alors P ⇒ Q est vraie. — L’implication P ⇒ Q se lit aussi : si P alors Q. — Lorsque P ⇒ Q est vraie, on dit : « Q est une condition nécessaire de P » ou encore : « pour que P soit vraie il faut que Q soit vraie ; mais on dit aussi : « P est une condition suffisante de Q » ou encore : « pour que Q soit vraie il suffit que P soit vraie ». 2. P ⇔ Q est vraie uniquement lorsque P et Q portent la même valeur de vérité. Exemples 1.2 √1. « 3 est un entier pair ⇒ 3 = 5 » est une assertion vraie. 2. « π ∈ / Q ⇒ 2 < 1 » est une assertion fausse. Proposition 1.2 Principe de non-contradiction : La proposition : (P et ¬P) est fausse. Toute assertion de cette forme est appelée une contradiction. Principe du tiers exclu : L’assertion : (P ou ¬P) est vraie. Propriétés 1.3 Soient P , Q et R trois assertions. Les assertions suivantes sont toujours vraies : (I) 1. (P et Q) ⇔ (Q et P) ; (P ou Q) ⇔ (Q ou P). 2. [(P et Q) et R] ⇔ [P et (Q et R)] ; [(P ou Q) ou R] ⇔ [P ou (Q ou R)]. 3. [P et (Q ou R)] ⇔ [(P et Q) ou (P et R)] ; [(P ou Q) et R] ⇔ [(P et R) ou (Q et R)]. 4. [P ou (Q et R)] ⇔ [(P ou Q) et (P ou R)] ; [(P et Q) ou R] ⇔ [(P ou R) et (Q ou R)]. (II) 1. ¬(¬P) ⇔ P. 2. ¬(P et Q) ⇔ (¬P ou ¬Q). 3. ¬(P ou Q) ⇔ (¬P et ¬Q). (III) 1. (P ⇒ Q) ⇔ (¬P ou Q). 2. ¬(P ⇒ Q) ⇔ (P et ¬Q). 3. (P ⇒ Q) ⇔ (¬Q ⇒ ¬P) contraposée. 4. [(P ⇒ Q) et (Q ⇒ R)] ⇒ (P ⇒ R) transitivité. (IV) (P ⇔ Q) ⇔ [(P ⇒ Q) et (Q ⇒ P)]. Remarque 1.4 Pour montrer P ⇒ Q on a trois méthodes : 1. méthode directe : on suppose que P est vraie et on montre que Q est vraie. 2. méthode par contraposée : on suppose que Q est fausse et on montre que P est fausse. 3. méthode par l’absurde : à voir bien tôt. Exemple 1.1 Soit n ∈ N. Montrer : n est pair ⇔ n2 est pair.  1.1 Éléments de logique 7 1.1.3 Raisonnement par l’absurde On cherche à montrer qu’une assertion P est vraie, pour cela, on suppose que P est fausse et on montre que cela entraîne une contradiction avec une assertion Q qu’on sait déjà qu’elle est vraie. √ Exemple 1.2 Montrer : 2 ∈ / Q. Remarque 1.5 Pour montrer P ⇒ Q par l’absurde : on suppose le contraire de P ⇒ Q, c’est-à-dire on suppose « P et ¬Q »(i.e. P est vraie et Q est fausse). On montre alors que ceci conduit à une contradiction. √ Exemple 1.3 On rappelle que 2 est un nombre irrationnel. Soient a et b deux entiers √ relatifs. Montrer que : a + b 2 = 0 =⇒ a = b = 0. 1.1.4 Raisonnement par équivalences successives Le raisonnement par équivalences successives repose sur l’équivalence suivante : [(P ⇔ Q) et (Q ⇔ R)] ⇔ (P ⇔ R). Exemple 1.4 Cherchons les solutions réelles de l’équation : (E) x3 − 9x = 0 1.1.5 Raisonnement par disjonction des cas Exemple 1.5 — Raisonnement par disjonction des cas. Soit x ∈ R. montrer que : | x − 2 |≤ x2 − x + 2 1.1.6 Raisonnement par analyse-synthèse Le raisonnement par analyse-synthèse est utilisé lorsqu’on cherche la ou les solutions à un problème. Il se déroule en deux étapes : l’analyse : on suppose que l’on a une solution du problème et on cherche à en déduire toutes les propriétés possibles de cette solution, l’objectif étant d’essayer de l’identifier au mieux ; la synthèse : elle consiste à déterminer parmi tous les objets mathématiques ayant les propriétés requises (obtenues lors de l’analyse), ceux qui sont effectivement solutions du problème. Exemple 1.6 Prouver que toute fonction f définie sur R s’écrit de manière unique comme somme d’une fonction paire g et d’une fonction impaire h.. 1.1.7 Quantificateurs Ensembles — Un ensemble E est une collection d’objets, chaque objet x de E est dit un élément de E et on écrit x ∈ E. — L’ensemble vide est celui qui ne contient aucun élément et il est noté 0. / — Un ensemble qui contient un seul élément x est appelé un singleton et est noté {x}. Prédicats Un prédicat est un énoncé mathématique qui contient (au moins) une variable d’un certain ensemble tel que lorsqu’on attribue une valeur à chacune des variables y figurant, on obtient une assertion. Exemples 1.3 1. « n2 + 1 est un nombre premier » est un prédicat dont la variable n appartient à N. 2. x2 + x + 1 + y2 = 0 est un prédicat à deux variables, chacune d’entre elles appartient à C.  8 Chapitre 1. Éléments de logique et vocabulaire ensembliste Quantificateurs Soit P(x) un prédicat à une variable x d’un ensemble E. On peut alors construire : — l’assertion : (∀x ∈ E) P(x) * qui se lit « pour tout x de E, on a P(x) », * qui, par définition, vraie lorsque l’assertion P(a) est vraie pour tout élément a de E ; le symbole « ∀ » est appelé quantificateur universel ; — l’assertion : (∃x ∈ E) P(x) * qui se lit « il existe un x de E tel que P(x) », * qui, par définition, est vraie lorsqu’il existe (au moins) un élément a de E tel que l’assertion P(a) soit vraie ; le symbole « ∃ » est appelé quantificateur existentiel. Remarque 1.6 L’assertion (∃!x ∈ E) P(x) se lit « il existe un unique x ∈ E tel que P(x) » et elle est vraie lorsqu’il existe un et un seul élément a de E tel que l’assertion P(a) soit vraie. Exemples 1.4 1. L’assertion « (∀x ∈ R) x2 + 1 ≥ 0 » est vraie. 2. L’assertion « (∀x ∈ R) x2 − 1 ≥ 0 » est fausse. 3. L’assertion « (∃x ∈ R) x2 − 1 ≥ 0 » est vraie. La négation de « (∀x ∈ E) P(x) » est « (∃x ∈ E) ¬P(x) » et la négation de « (∃x ∈ E) P(x) » est « (∀x ∈ E) ¬P(x) ». Exemple 1.7 Écrire la négation de : A : (∀x ∈ R)(∃n ∈ N) n > x. B : (∀ε > 0)(∃α > 0)(∀x ∈ R) (|x − 1| ≤ α ⇒ |x2 − 1| ≤ ε). Remarque 1.7 L’ordre des quantificateurs de nature différente est essentiel. Exploiter une hypothèse du type « ∀x ∈ E, P(x) » Exercice 1.1 Soient α, β ∈ R. On suppose que : ∀x ∈ R, α cos x + β sin x = 0. Montrer : α = β = 0. Montrer une assertion de la forme « ∃x ∈ E, P(x) » Exercice : Soient a et b deux réels tels que a < b. Montrer qu’il existe un réel tel que a < x < b. 1.2 Opérations sur les ensembles 1.2.1 Inclusion Soient E et F deux ensembles quelconques. On écrit — E ⊂ F pour signifier : ∀x, x ∈ E ⇒ x ∈ F; — E = F pour signifier : ∀x, x ∈ E ⇔ x ∈ F. Propriétés 1.8 Soient E, F et G trois ensembles. 1. 0/ ⊂ E ; E ⊂ E. 2. (E = F) ⇔ (E ⊂ F et F ⊂ E). 3. (E ⊂ F et F ⊂ G) ⇒ (E ⊂ G).  1.2 Opérations sur les ensembles 9 1.2.2 Ensemble des parties d’un ensemble Soit E un ensemble quelconque, l’ensemble des parties de E, noté P(E), est défini par : X ∈ P(E) ⇔ X ⊂ E. Exemple1.8 E = {a, b, c}.  P(E) = 0, / {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, E. Remarque 1.9 P(E) n’est jamais vide car 0/ ∈ P(E) et E ∈ P(E). 1.2.3 Intersection et réunion Soient E et F deux ensembles. On définit l’intersection E ∩ F et la réunion E ∪ F de E et F par : E ∩ F = {x | x ∈ E et x ∈ F} ; E ∪ F = {x | x ∈ E ou x ∈ F}. E ∩ 0/ = 0/ ; E ∪ 0/ = E; E ∩E = E ; E ∪ E = E; Remarque 1.10 E ∩F = F ∩E ; E ∪ F = F ∪ E; E ∩ F ⊂ E et E ∩ F ⊂ F ; E ⊂ E ∪ F et F ⊂ E ∪ F. Définition 1.4 On dit que deux ensembles E et F sont disjoints si E ∩ F = 0. / Propriétés 1.11 Soient E, F et G trois ensembles. Alors 1. E ∩ F = E ⇔ E ⊂ F ; E ∪ F = E ⇔ F ⊂ E. 2. (E ∩ F) ∩ G = E ∩ (F ∩ G) ; (E ∪ F) ∪ G = E ∪ (F ∪ G). 3. E ∩ (F ∪ G) = (E ∩ F) ∪ (E ∩ G) ; (E ∪ F) ∩ G = (E ∩ G) ∪ (F ∩ G). 4. E ∪ (F ∩ G) = (E ∪ F) ∩ (E ∪ G) ; (E ∩ F) ∪ G = (E ∪ G) ∩ (F ∪ G). 1.2.4 Différence et différence symétrique Définition 1.5 — Différence, complémentaire. Soient E et F deux ensembles. — On appelle différence de E et F, l’ensemble, noté E\F, des éléments qui sont dans E mais pas dans F; on a donc x ∈ E\F ⇔ (x ∈ E et x ∈ / F.) — Lorsque F ⊂ E, l’ensemble E\F s’appelle complémentaire de F dans E, et il se note CFE ou F. Propriétés 1.12 Soient A et B deux parties d’un même ensemble Ω, A = CAΩ et B = CBΩ. Alors 1. A = A ; A ∩ A = 0/ ; A ∪ A = Ω. 2. A ⊂ B ⇔ B ⊂ A. 3. A ∩ B = 0/ ⇔ B ⊂ A ⇔ A ⊂ B. 4. A ∪ B = A ∩ B ; A ∩ B = A ∪ B. 5. A\B = A ∩ B.  10 Chapitre 1. Éléments de logique et vocabulaire ensembliste Définition 1.6 — Différence symétrique. Soient E et F deux ensembles. On appelle différence symétrique de E et F, l’ensemble, noté E∆F, défini par : E∆F = (E\F) ∪ (F\E). Propriétés 1.13 Soient A, B et C trois ensembles. Alors 1. A∆B = (A ∪ B)\(A ∩ B). 2. (A∆B)∆C = A∆(B∆C). (∆ est associative) Démonstration. À faire en ex. 1.2.5 Couple, produit cartésien À partir de deux éléments x, y, on peut construire le couple (x, y) avec, si x1 , y1 , x2 et y2 sont des éléments, la propriété fondamentale : (x1 , y1 ) = (x2 , y2 ) ⇔ (x1 = x2 et y1 = y2 ). Définition 1.7 — Produit cartésien. Soient E et F deux ensembles. On appelle produit cartésien de E et F, l’ensemble, noté E × F, des couples (x, y) avec x ∈ E et y ∈ F. On a donc E × F = {(x, y) | x ∈ E et y ∈ F}. Ainsi, on a : z ∈ E × F ⇐⇒ (∃x ∈ E , ∃y ∈ F / z = (x, y)). Exercice 1.2 Décrire E × F lorsque E = {1, 2} et F = {1, 2, 3}. Propriétés 1.14 Soient E, F et G trois ensembles. Alors 1. E × F = 0/ ⇔ (E = 0/ ou F = 0). / 2. E × (F ∪ G) = (E × F) ∪ (E × G) ; (E ∪ F) × G = (E × G) ∪ (F × G). 3. E × (F ∩ G) = (E × F) ∩ (E × G) ; (E ∩ F) × G = (E × G) ∩ (F × G). Remarque 1.15 Si x ̸= y, alors (x, y) ̸= (y, x). E ×F = ̸ F × E, lorsque E et F sont distincts et non vides. Définition 1.8 Soient n ∈ N∗ , n ≥ 2 et E1 , E2 ,... , En des ensembles. — On définit le produit cartésien E1 × E2 ×... En par : E1 × E2 ×... En = {(x1 , x2 ,... , xn ) | x1 ∈ E1 , x2 ∈ E2 ,... , xn ∈ En }. — (x1 , x2 ,... , xn ) s’appelle un n-uplet. — Si E1 = E2 = · · · = En = E, alors E1 × E2 ×... En est noté E n. Exemple 1.9 Soit E = {0, 1}. Décrire E 3.  2. Relations binaires et applications 2.1 Graphe - Correspondance Définition 2.1 Soient E et F deux ensembles non vides. On appelle graphe de E vers F, toute partie non vide Γ de E × F. Exemple 2.1 E = {a, b, c, d} , F{0, 1, 2}. Γ = {(a, 0), (a, 1), (c, 1), (c, 2), (d, 2)} est un graphe de E vers F. Définition 2.2 Soient E et F deux ensembles non vides. — On appelle correspondance (ou relation) de E vers F, tout triplet R = (E, F, Γ) où Γ est un graphe de E vers F. — E s’appelle l’ensemble de départ, F l’ensemble d’arrivé de la correspondance R. — L’ensemble de définition de R, noté DR , est défini par : DR = {x ∈ E | ∃y ∈ F, (x, y) ∈ Γ}. — L’ensemble des valeurs de R, noté VR , est défini par : VR = {y ∈ F | ∃x ∈ E, (x, y) ∈ Γ}. Dans l’exemple précédent, on a : DR = {a, c, d} et VR = F. 2.2 Relations binaires 2.2.1 Définitions et exemples  12 Chapitre 2. Relations binaires et applications Définition 2.3 Soit E un ensemble non vide. On appelle relation binaire sur E toute correspondance R = (E, E, Γ) de E vers E. Si (x, y) ∈ Γ, on dit que x est en relation avec y ; on note xRy. Exemples 2.1 1. Soient E un ensemble. xRy si, et seulement si, x = y est une relation binaire sur E. 2. La relation d’inclusion est une relation binaire dans l’ensemble P(E). Définition 2.4 Soient E un ensemble non vide et R une relation binaire sur E. On dit que : 1. R est réflexive si ∀x ∈ E, xRx. 2. R est symétrique si ∀(x, y) ∈ E 2 , xRy ⇒ yRx. 3. R est antisymétrique si ∀(x, y) ∈ E 2 , (xRy et yRx) ⇒ x = y. 4. R est transitive si ∀(x, y, z) ∈ E 3 , (xRy et yRz) ⇒ xRz. Exemples 2.2 1. La relation d’égalité de l’exemple précédent est réflexive, symétrique et transitive. 2. Dans l’ensemble P(E), l’inclusion est réflexive, antisymétrique et transitive. 2.2.2 Relations d’équivalence Définition 2.5 Soit E un ensemble non vide. On appelle relation d’équivalence sur E toute relation binaire sur E qui est à la fois réflexive, symétrique et transitive. Exemples 2.3 1. L’égalité dans E, (xRy ⇔ x = y) est une relation d’équivalence. 2. Soit n ∈ N tel que n ≥ 2. Dans Z, on définit la relation binaire Rn par : ∀(x, y) ∈ Z2 , xRn y ⇔ n divise x − y (c’est-à-dire : ∃k ∈ Z, x − y = kn). Rn est une relation d’équivalence. Définition 2.6 Soit R une relation d’équivalence sur un ensemble E et x ∈ E.. On appelle classe d’équivalence de x modulo R, que l’on note cℓR (x) ou x̄ ou x, l’ensemble défini par : cℓR (x) = {y ∈ E | yRx}. L’ensemble des classes d’équivalences modulo R est appelé ensemble-quotient de E par R; on le note E/R. Si y ∈ cℓR (x), on dit que y est représentant de cℓR (x). On appelle ensemble de représentants pour la relation R une partie C de E vérifiant ∀x ∈ E, ∃!y ∈ C : : xRy. Exemple 2.2 Dans Z muni de la relation d’équivalence Rn déterminer x̄ pour tout x ∈ Z. L’ensemble quotient est noté Z/nZ. Proposition 2.1 Étant donné une relation d’équivalence R sur un ensemble E. 1. Soient x et y deux éléments de E. Les propriétés suivantes sont équivalentes : (i) xRy (ii) y ∈ x̄ (iii) x̄ = ȳ.  2.2 Relations binaires 13 2. Pour tous x, y ∈ E, on a : x̄ = ȳ ou x̄ ∩ ȳ = 0. / Démonstration. Exemple 2.3 On reprend l’exemple précédent. L’ensemble des représentants pour la relation Rn est {0, 1,... , n − 1}. Ainsi, Z/nZ = {0,... , n − 1}. 2.2.3 Relations d’ordre Définitions et exemples Définition 2.7 Soit E un ensemble non vide. On appelle relation d’ordre sur E, toute relation binaire R sur E qui est à la fois réflexive, antisymétrique et transitive. R est souvent notée ≤ et le couple (E, ≤) est alors appelé ensemble ordonné. Exemples 2.4 1. Les relations d’ordres usuelles sur N, Z, Q ou R notées ≤ ou ≥. 2. La relation d’inclusion sur P(E). Définition 2.8 Soit (E, ≤) un ensemble ordonné. — On dit que (E, ≤) est totalement ordonné (ou que ≤ est une relation d’ordre totale) si : ∀x, y ∈ E, (x ≤ y ou y ≤ x). — Un ordre qui n’est pas total est dit partiel. Exemples 2.5 1. La relation d’ordre usuelle sur R, et donc sur N, Z et Q est totale. 2. Soit E un ensemble qui contient au moins deux éléments distincts a et b. Dans P(E), l’inclusion est une relation d’ordre partiel. En effet : {a} et {b} ne sont pas comparables. 3. Dans N, la relation de divisibilité définie par : x | y ⇔ ∃k ∈ N, y = kx est une relation d’ordre partiel. 4. Dans Z, la relation de divisibilité n’est pas antisymétrique. Éléments remarquables dans un ensemble ordonné Définition 2.9 Soit (E, ≼) un ensemble ordonné. — S’il existe un élément a ∈ E tel que : ∀x ∈ E, a ≼ x =⇒ x = a on dit que a est une élément maximal de E. — S’il existe un élément a ∈ E tel que : ∀x ∈ E, x ≼ a =⇒ x = a on dit que a est une élément minimal de E. Exemple 2.4 Dans N \ {1} muni de la division ”|” les éléments minimaux sont les nombres premiers. Dans N muni de la division ”|” 0 est le seul élément maximal. Définition 2.10 Soient (E, ≼) un ensemble ordonné, A une partie non vide de E et a ∈ A. — a est le plus grand élément de A si ∀x ∈ A, x ≼ a.  14 Chapitre 2. Relations binaires et applications Quand il existe, le plus grand élément de A, qui est unique, se note max(A). — a est le plus petit élément de A si ∀x ∈ A, a ≼ x. Quand il existe, le plus petit élément de A, qui est unique, se note min(A). Exemple 2.5 Soit E un ensemble. Dans (P(E), ⊂), on a : min(P(E)) = 0/ et max(P(E)) = E. Définition 2.11 Soient (E, ≤) un ensemble ordonné et A une partie non vide de E. — On dit que A est majorée si ∃M ∈ E, ∀x ∈ A, x ≤ M. (M est appelé un majorant de A) — On dit que A est minorée si ∃m ∈ E, ∀x ∈ A, m ≤ x. (m est appelé un minorant de A) Définition 2.12 Soient (E, ≤) un ensemble ordonné et A une partie non vide de E. — On dit que A admet une borne supérieure si l’ensemble des majorants admet un plus petit élément α, et dans ce cas α est appelé la borne supérieure de A et se note sup(A). — On dit que A admet une borne inférieure si l’ensemble des minorants admet un plus grand élément β , et dans ce cas β est appelé la borne inférieure de A et se note inf(A). Exemples 2.6 (E, ≤) = (R, ≤) 1. A =]0,  1[; sup(A)= 1; inf(A) = 0. 1 2. A = | n ∈ N∗ ; sup(A) = max(A) = 1; inf(A) = 0. n Remarque 2.2 1. (a) La borne sup lorsqu’elle existe c’est le plus petit des majorants. (b) La borne inf lorsqu’elle existe c’est le plus grand des minorants. (c) sup(A) et inf(A) n’appartiennent pas forcement à A. 2. (a) Si A admet un plus grand élément alors sup(A) = max(A). (b) Si A admet un plus petit élément alors inf(A) = min(A). 2.3 Raisonnement par récurrence 2.3.1 Principe de récurrence L’ensemble N des entiers naturels est un ensemble non vide, muni d’une relation d’ordre total ainsi qu’une addition et d’une multiplication compatible avec cette relation d’ordre, i.e. vérifiant : ∀(x, y, z) ∈ N3 , x ≤ y =⇒ (x + z ≤ y + z et xz ≤ yz). De plus : toute partie non vide de N possède un plus petit élément ; toute partie non vide majorée de N possède un plus grand élément ; N n’est pas majoré. Principe de récurrence : Soit A une partie de N. Alors, on a :  0 ∈ A  Si et alors A = N.  ∀n ∈ N, (n ∈ A ⇒ n + 1 ∈ A)  2.3.2 Récurrence simple  2.3 Raisonnement par récurrence 15 Théorème 2.3 Soit P(n) une proposition de variable n ∈ N et n0 ∈ N. Si Initialisation : l’assertion P(n0 ) est vraie, Hérédité : pour tout entier n ≥ n0 , P(n) implique P(n + 1); alors la proposition P(n) est vraie pour tout entier n ≥ n0. n n(n + 1) Exemple 2.6 Montrer que, pour tout entier n ∈ N⋆ , ∑k= k=1 2 2.3.3 Récurrence double Théorème 2.4 Soit P(n) une proposition de variable n ∈ N et n0 ∈ N. Si Initialisation : les assertions P(n0 ) st P(n0 + 1) sont vraies, Hérédité : pour tout entier n ≥ n0 , P(n) et P(n + 1) implique P(n + 2); alors la proposition P(n) est vraie pour tout entier n ≥ n0. Exemple 2.7 Soit (un ) la suite définie par u0 = 1, u1 = −5 et, pour tout n ∈ N, un+2 = 5un+1 − 6un. Montrer que, pour tout entier n ∈ N, un = 4 × 2n+1 − 7 × 3n. — Initialisation : On a u0 = 1 = 4 × 20+1 − 7 × 30 et u1 = −5 = 4 × 21+1 − 7 × 31 , donc la propriété est vérifiée pour n = 0 et pour n = 1. — Hérédité : Soit n ∈ N. Supposons un = 4 × 2n+1 − 7 × 3n et un+1 = 4 × 2n+2 − 7 × 3n+1. Montrons un+2 = 4 × 2n+3 − 7 × 3n+2. On a : un+2 = 5un+1 − 6un = 5(4 × 2n+2 − 7 × 3n+1 ) − 6(4 × 2n+1 − 7 × 3n ) = 10 × 2n+3 − 35 × 3n+1 − 6 × 2n+3 + 14 × 3n+1 = 4 × 2n+3 − 21 × 3n+1 = 4 × 2n+3 − 7 × 3n+2 Donc, un+2 = 4 × 2n+3 − 7 × 3n+2. — Conclusion : ∀n ∈ N, un = 4 × 2n+1 − 7 × +3n 2.3.4 Récurrence forte Théorème 2.5 Soit P(n) une proposition de variable n ∈ N et n0 ∈ N. Si Initialisation : l’assertion P(n0 ) est vraie, Hérédité : pour tout entier n ≥ n0 , P(n0 ) et P(n0 + 1) et... et P(n) implique P(n + 1);
alors la proposition P(n) est vraie pour tout entier n ≥ n0. 2 n Exemple 2.8 Soit (un )n∈N⋆ la suite définie par u1 = π et pour tout entier n ∈ N⋆ , un+1 = ∑ uk. n k=1 Montrer que, pour tout entier n ∈ N⋆ , un = nπ. On va procéder par récurrence forte sur n ∈ N∗. Pour n ∈ N∗ , on note P(n) la propriété « un = πn ». — Initialisation : On a u1 = π et donc P(1) est vraie.  16 Chapitre 2. Relations binaires et applications — Hérédité : Soit n ∈ N∗ et supposons que ∀k ∈ J1, nK, uk = kπ. Alors 2 n un+1 = ∑ uk n k=1 2 n = ∑ kπ n k=1 2π n(n + 1) = × n 2 n n(n + 1) car ∑k=. On en déduit que un+1 = π(n + 1), et donc que P(n + 1) est vraie. k=1 2 — Conclusion : ∀n ∈ N∗ , un = nπ. 2.3.5 Récurrence finie Théorème 2.6 Soient P(n) une proposition de variable n ∈ N et n0 , m ∈ N tels que n0 < m. Si Initialisation : l’assertion P(n0 ) est vraie, Hérédité : pour tout entier n ∈ Jn0 , m − 1K, P(n) implique P(n + 1); alors la proposition P(n) est vraie pour tout entier n ∈ Jn0 , mK. ( R −→ R Exemple 2.9 Soient n ∈ N⋆ et f : x 7−→ (x2 − 1)n Montrer que, pour tout entier k ∈ J0, n − 1K, f (k) (1) = 0. L’étude des premières valeurs de k laisse penser que, pour k ∈ J0, nK, on peut mettre (x − 1)n−k en facteur dans f (k) (x). Montrons-le par récurrence finie. Pour tout k ∈ J0, nK, désignons par Hk la propriété : « il existe une fonction polynomiale gk telle que ∀x ∈ R, f (k) (x) = (x − 1)n−k gk (x). » — Initialisation : H0 est évidemment vraie : il suffit de prendre g0 : x 7→ (x + 1)n. — Hérédité : Soit k ∈ J0, n − 1K tel que Hk soit vraie. On peut donc trouver une fonction polynomiale gk telle que : ∀x ∈ R f (k) (x) = (x − 1)n−k gk (x). Étant donné que gk est polynomiale, donc dérivable, et que n − k ⩾ 1, on en déduit par dérivation : ∀x ∈ R f (k+1) (x) = (x − 1)n−k−1 (n − k)gk (x) + (x − 1)g′k (x).
Si l’on pose alors : ∀x ∈ R gk+1 (x) = (n − k)gk (x) + (x − 1)g′k (x), on définit une fonction polynomiale gk+1 vérifiant : ∀x ∈ R f (k+1) (x) = (x − 1)n−k−1 gk+1 (x), ce qui prouve Hk+1. — Conclusion : pour tout k ∈ J0, n − 1K, on a : ∀x ∈ R f (k) (x) = (x − 1)n−k gk (x). Comme n − k ⩾ 1, on en déduit f (k) (1) = 0. 2.3 Raisonnement par récurrence 17 Remarque 2.7 La notion de racine multiple d’un polynôme permettra d’avoir une démonstration plus efficace du résultat précédent.