Éléments de logique, récurrence, sommes et produits

Résumé en cinq points

1Éléments de logique

1.1Proposition et connecteurs

« 5 est un nombre premier » est une proposition vraie. « $x > 0$ » n'en est pas une tant que $x$ n'est pas fixé ou quantifié.

À partir de deux propositions $P$ et $Q$ on construit :

• « non $P$ », vraie exactement quand $P$ est fausse ;
• « $P$ et $Q$ », vraie quand les deux sont vraies ;
• « $P$ ou $Q$ », vraie dès que l'une au moins est vraie. Le « ou » des mathématiques est inclusif.

1.2Implication, réciproque, contraposée

Trois conséquences :

• La négation de $P \Rightarrow Q$ est « $P$ et non $Q$ ». Pour réfuter une implication, on exhibe un contre-exemple, c'est-à-dire un cas où l'hypothèse est vérifiée et la conclusion fausse.
• La réciproque de $P \Rightarrow Q$ est $Q \Rightarrow P$. Elle n'a aucune raison d'être vraie.
• La contraposée de $P \Rightarrow Q$ est « non $Q \Rightarrow$ non $P$ ». Une implication et sa contraposée sont vraies ou fausses en même temps.

1.3Quantificateurs

Les quantificateurs ne sont pas des abréviations de français. On écrit soit une phrase entièrement en français, soit une formule entièrement symbolique.

1.4Les modes de raisonnement

• Raisonnement direct. On suppose $P$ et on déduit $Q$ par une chaîne d'implications.
• Par contraposée. Pour établir $P \Rightarrow Q$, on établit « non $Q \Rightarrow$ non $P$ ».
• Par l'absurde. Pour établir $P$, on suppose « non $P$ » et on aboutit à une contradiction.
• Par disjonction de cas. On découpe la situation en cas exhaustifs.
• Par analyse-synthèse. L'analyse suppose l'objet trouvé et en déduit sa forme, ce qui donne des candidats. La synthèse vérifie lesquels conviennent. C'est le raisonnement type pour les problèmes d'existence et d'unicité.
• Par contre-exemple. Un seul contre-exemple réfute une propriété universelle.

2Raisonnement par récurrence

2.1Récurrence simple

Le programme exclut tout exposé théorique sur le principe de récurrence. On l'utilise comme un outil admis.

2.2Variantes

3Notations somme et produit

3.1Définitions et manipulations

Conventions :

• une somme vide vaut 0, un produit vide vaut 1 ;
• l'indice est muet : $\sum_{i=1}^{n} u_i$ et $\sum_{k=1}^{n} u_k$ désignent le même nombre ;
• un indice muet ne doit jamais apparaître dans le résultat.

Changement d'indice : en posant $j = i - 1$ ou $j = n - i$, on décale ou on retourne une somme. Il faut à chaque fois recalculer les bornes.

À repérer dès qu'un terme général s'écrit comme une différence de deux valeurs consécutives d'une même suite.

Sommes doubles : $\sum_{1 \leqslant i \leqslant n} \sum_{1 \leqslant j \leqslant n} u_{i,j}$ se manipule en échangeant l'ordre des sommations, ce qui est licite pour des sommes finies. Attention quand les bornes de la seconde dépendent de l'indice de la première.

3.2Sommes de référence

Les formules donnant $\sum k^2$ et $\sum k^3$ se voient en exercice. Le programme précise qu'elles ne sont pas exigibles. On sait les retrouver par récurrence si l'énoncé les fournit.

4Factorielle et coefficients binomiaux

4.1Factorielle

4.2Coefficients binomiaux

Formules exigibles :

• Symétrie : $\binom{n}{p} = \binom{n}{n-p}$.
• Formule du pion, valable pour $p \geqslant 1$ : $p\binom{n}{p} = n\binom{n-1}{p-1}$.
• Formule de Pascal : $\binom{n}{p} + \binom{n}{p+1} = \binom{n+1}{p+1}$.

La formule de Pascal fait fonctionner le triangle de Pascal, où chaque coefficient est la somme des deux qui sont au-dessus de lui.

Valeurs à connaître : $\binom{n}{0} = \binom{n}{n} = 1$ et $\binom{n}{1} = \binom{n}{n-1} = n$.

Lien avec l'arbre binaire de terminale : $\binom{n}{p}$ est le nombre de chemins réalisant $p$ succès en $n$ répétitions. C'est exactement ce qui donnera la loi binomiale.

4.3Formule du binôme de Newton

La démonstration se fait par récurrence sur $n$, en utilisant la formule de Pascal lors du regroupement des termes.

Deux cas particuliers utiles :

• avec $a = b = 1$ : $\sum_{k=0}^{n} \binom{n}{k} = 2^n$, ce qui redonne le nombre de parties d'un ensemble à $n$ éléments ;
• avec $a = -1$ et $b = 1$ : la somme alternée des coefficients binomiaux est nulle dès que $n \geqslant 1$.

Méthodes

Ce qu'il faut savoir refaire en khôlle

1. Écrire la négation de la définition quantifiée de la convergence d'une suite.
2. Donner un contre-exemple à une réciproque proposée par l'examinateur.
3. Démontrer par contraposée que si $n^2$ est pair alors $n$ est pair.
4. Rédiger une récurrence simple et une récurrence double en nommant les trois étapes.
5. Calculer $\sum_{k=0}^{n} q^k$ en distinguant les cas $q = 1$ et $q \neq 1$.
6. Calculer une somme télescopique, par exemple $\sum \frac{1}{k(k+1)}$.
7. Démontrer la formule de Pascal à partir de l'expression factorielle.
8. Démontrer la formule du binôme par récurrence, et en déduire $\sum \binom{n}{k} = 2^n$.

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). Exigible, à savoir justifier par une table de vérité ou par le sens.
• Une implication P ⇒ Q est fausse dans le seul cas où P est vraie et Q fausse. Sa négation est (P et non Q). Exigible.
• Une implication et sa contraposée non Q ⇒ non P sont équivalentes. Sa réciproque Q ⇒ P n'a aucun lien avec elle. Exigible.
• Négation d'une phrase quantifiée. On échange chaque ∀ en ∃ et chaque ∃ en ∀ dans l'ordre d'apparition, puis on nie la proposition finale. Exigible, c'est le test de khôlle numéro un.
• Principe de récurrence, simple, double ou forte. Admis, aucune théorie n'est au programme. La rédaction en trois étapes nommées est exigible.
• Somme des premiers entiers, Σ_k=1ⁿ k = n(n + 1)/2. Exigible avec démonstration, par récurrence ou par la somme écrite dans les deux sens.
• Somme géométrique, pour q ≠ 1, Σ_k=0ⁿ q^k = (1 − qⁿ⁺¹)/(1 − q), et n + 1 si q = 1. Exigible avec démonstration, par récurrence ou par multiplication par (1 − q).
• Les formules Σ_k=1ⁿ k² = n(n + 1)(2n + 1)/6 et Σ_k=1ⁿ k³ = (n(n + 1)/2)² se voient en exercice. Non exigibles, un énoncé de concours les fournit ou les fait établir par récurrence.
• Télescopage, Σ_k=1ⁿ (a_k+1 − a_k) = a_n+1 − a₁. Exigible, immédiat en écrivant les termes.
• Définition de n!, avec 0! = 1 et n! = n × (n − 1)!. Exigible.
• Coefficients binomiaux, C(n, p) = n!/(p!(n − p)!) pour 0 ≤ p ≤ n, et C(n, p) = 0 par convention si p > n. Symétrie C(n, p) = C(n, n − p). Exigibles.
• Formule de Pascal, C(n, p) + C(n, p + 1) = C(n + 1, p + 1). Exigible avec démonstration, par calcul sur les factorielles.
• Formule du pion, p C(n, p) = n C(n − 1, p − 1) pour 1 ≤ p ≤ n. Exigible, elle figure au paragraphe sur les ensembles.
• Formule du binôme de Newton, (a + b)ⁿ = Σ_k=0ⁿ C(n, k) a^k b^n−k pour a, b réels. Exigible avec démonstration par récurrence et formule de Pascal.
• Hors programme, à signaler si un exercice les demande, la formule de Vandermonde comme résultat de cours, les nombres complexes, et toute axiomatique de N.

Clés de démonstration

Somme des premiers entiers. On écrit S = 1 + 2 + … + n, puis S = n + (n − 1) + … + 1, et on additionne terme à terme, chaque colonne vaut n + 1, il y a n colonnes, donc 2S = n(n + 1). Astuce, le retournement d'indice j = n + 1 − k est la version propre de ce « double écriture ».

Somme géométrique. On pose S = Σ_k=0ⁿ q^k et on calcule qS = Σ_k=1ⁿ⁺¹ q^k après le changement d'indice j = k + 1. Alors S − qS = 1 − qⁿ⁺¹, tous les termes intermédiaires disparaissent. Si q ≠ 1 on divise. Astuce, c'est un télescopage caché, et le cas q = 1 se traite à part.

Formule de Pascal. On réduit au même dénominateur (p + 1)!(n − p)! les deux fractions n!/(p!(n − p)!) et n!/((p + 1)!(n − p − 1)!). Le numérateur devient n!((p + 1) + (n − p)) = (n + 1)!. Astuce, multiplier haut et bas de chaque fraction par le facteur manquant, jamais développer les factorielles.

Binôme de Newton. Initialisation avec n = 0. Hérédité, on multiplie (a + b)ⁿ développé par (a + b), on obtient deux sommes, on décale l'indice de la première pour aligner les puissances de a, on regroupe avec Pascal, on traite à part les termes extrêmes k = 0 et k = n + 1. Astuce, écrire les deux sommes avec le même indice de sommation avant de les additionner.

Négation d'une convergence. La définition « ∀ε > 0, ∃n₀ ∈ N, ∀n ≥ n₀, |u_n − l| ≤ ε » se nie mécaniquement en « ∃ε > 0, ∀n₀ ∈ N, ∃n ≥ n₀, |u_n − l| > ε ». Astuce, ne pas chercher à comprendre avant d'avoir fini, la mécanique d'abord, le sens ensuite.

Exemples et contre-exemples à connaître

1. « ∀x ∈ R, ∃y ∈ R, y > x » est vraie, « ∃y ∈ R, ∀x ∈ R, y > x » est fausse. On ne permute jamais un ∀ et un ∃.
2. « n multiple de 6 ⇒ n pair » est vraie, sa réciproque est fausse avec n = 4. Réciproque et contraposée ne se confondent pas.
3. « Si 0 = 1 alors 2 = 5 » est une implication vraie. Une hypothèse fausse rend l'implication vraie.
4. La propriété « n = n + 1 » est héréditaire et jamais vraie. Sans initialisation, une récurrence ne prouve rien.
5. La propriété « 2ⁿ ≥ n² » est vraie pour n = 0, 1, 2, fausse pour n = 3, puis vraie pour n ≥ 4. Une récurrence s'initialise au bon rang, ici 4, pas à 0.
6. Σ_k=1ⁿ 1 = n mais Σ_k=0ⁿ 1 = n + 1. Compter les termes évite la moitié des erreurs de sommes.
7. Σ_k=0ⁿ 1^k = n + 1, alors que la formule (1 − qⁿ⁺¹)/(1 − q) donne 0/0. Le cas q = 1 est obligatoire.
8. (a + b)ⁿ ne vaut pas aⁿ + bⁿ dès que n ≥ 2 et ab ≠ 0. Pour n = 2 le terme croisé 2ab manque.
9. Σ_k=0ⁿ C(n, k) = 2ⁿ et Σ_k=0ⁿ (−1)^k C(n, k) = 0 pour n ≥ 1. Ce sont le binôme en (1, 1) et en (−1, 1).
10. La formule du binôme pour deux matrices exige AB = BA. Elle s'applique à (I + N)ⁿ, jamais à (A + B)ⁿ sans vérification.

Techniques du chapitre

Nier une phrase quantifiée. Mini-exercice, nier « f est bornée sur R », soit « ∃M ∈ R, ∀x ∈ R, |f(x)| ≤ M ». Négation, « ∀M ∈ R, ∃x ∈ R, |f(x)| > M ». Lecture, aussi grand que soit M, f le dépasse quelque part en valeur absolue.

Contraposée. Mini-exercice, montrer que si n² est impair alors n est impair. Contraposée, si n est pair, n = 2k, alors n² = 2(2k²) est pair. Deux lignes au lieu d'une discussion sur n².

Récurrence avec inégalité. Mini-exercice, montrer que pour tout n ≥ 4, 2ⁿ ≥ n². Initialisation, 16 ≥ 16. Hérédité, si 2ⁿ ≥ n² avec n ≥ 4, alors 2ⁿ⁺¹ ≥ 2n², et 2n² ≥ (n + 1)² équivaut à n² − 2n − 1 ≥ 0, vrai dès n ≥ 3. Conclusion pour tout n ≥ 4. L'initialisation à 4 est forcée par l'exemple 5.

Télescopage après décomposition. Mini-exercice, calculer Σ_k=1ⁿ 1/(k(k + 1)). On écrit 1/(k(k + 1)) = 1/k − 1/(k + 1), la somme vaut 1 − 1/(n + 1) = n/(n + 1).

Changement d'indice. Mini-exercice, exprimer Σ_k=2ⁿ⁺¹ q^k−2 avec la formule géométrique. On pose j = k − 2, j va de 0 à n − 1, la somme vaut (1 − qⁿ)/(1 − q) pour q ≠ 1. On recalcule toujours les deux bornes.

Somme double triangulaire. Mini-exercice, calculer Σ_{1 ≤ i ≤ j ≤ n} 1. Pour j fixé, i va de 1 à j, il y a j valeurs. La somme vaut Σ_j=1ⁿ j = n(n + 1)/2. On choisit l'indice extérieur, on fait courir l'autre.

Formule du pion. Mini-exercice, calculer Σ_k=0ⁿ k C(n, k). Le terme k = 0 est nul, puis k C(n, k) = n C(n − 1, k − 1), et la somme vaut n Σ_j=0ⁿ⁻¹ C(n − 1, j) = n 2ⁿ⁻¹ par le binôme.

Exercices classiques corrigés

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

Erreurs fréquentes