Cours et exercices corrigés de prépa BCPST : Logique, raisonnement par récurrence et dénombrement

1. Connecteurs, quantificateurs et négations

Pour des propositions $P$ et $Q$ :

• $\text{non}(P \text{ et } Q) \iff (\text{non } P) \text{ ou } (\text{non } Q)$ et $\text{non}(P \text{ ou } Q) \iff (\text{non } P) \text{ et } (\text{non } Q)$ ;
• $(P \Rightarrow Q) \iff (\text{non } P \text{ ou } Q)$, donc $\text{non}(P \Rightarrow Q) \iff (P \text{ et non } Q)$ ;
• la contraposée de $P \Rightarrow Q$ est $\text{non } Q \Rightarrow \text{non } P$ : elle lui est équivalente.

Négation des quantificateurs : $\text{non}(\forall x \in E,\ P(x)) \iff \exists x \in E,\ \text{non } P(x)$ et $\text{non}(\exists x \in E,\ P(x)) \iff \forall x \in E,\ \text{non } P(x)$. L'ordre des quantificateurs compte : $\forall x\ \exists y$ n'a pas le même sens que $\exists y\ \forall x$.

2. Types de raisonnement

• Contraposée : pour montrer $P \Rightarrow Q$, on montre $\text{non } Q \Rightarrow \text{non } P$.
• Absurde : on suppose $\text{non } P$ et on aboutit à une contradiction.
• Analyse-synthèse : on cherche les conditions nécessaires (analyse), puis on vérifie qu'elles conviennent (synthèse).
• Récurrence simple : 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$.
• Récurrence double : on initialise $P(n_0)$ et $P(n_0+1)$, puis on montre $(P(n) \text{ et } P(n+1)) \Rightarrow P(n+2)$. Elle sert pour les suites définies par deux termes précédents.

3. Sommes et produits

Sommes de référence, pour $n \in \mathbb{N}^{*}$ :
$$\sum_{k=1}^{n} k = \frac{n(n+1)}{2} \qquad \sum_{k=1}^{n} k^{2} = \frac{n(n+1)(2n+1)}{6} \qquad \sum_{k=0}^{n} q^{k} = \frac{1 - q^{n+1}}{1 - q} \ (q \neq 1)$$

• Changement d'indice : $\sum_{k=1}^{n} u_{k-1} = \sum_{j=0}^{n-1} u_{j}$.
• Télescopage : $\sum_{k=0}^{n} (u_{k+1} - u_{k}) = u_{n+1} - u_{0}$.
• Produits : $n! = \prod_{k=1}^{n} k$ avec $0! = 1$ ; $\prod_{k=1}^{n} a_k b_k = \prod a_k \times \prod b_k$ et $\prod_{k=1}^{n} \lambda = \lambda^{n}$.

4. Ensembles finis et cardinaux

Pour des ensembles finis $A$, $B$, $E$, $F$ :

• $\text{card}(A \cup B) = \text{card}(A) + \text{card}(B) - \text{card}(A \cap B)$ ;
• $\text{card}(E \times F) = \text{card}(E) \times \text{card}(F)$ ;
• si $\text{card}(E) = n$, l'ensemble $\mathcal{P}(E)$ des parties de $E$ a $2^{n}$ éléments ;
• si $A \subset E$, $\text{card}(\overline{A}) = \text{card}(E) - \text{card}(A)$.

Principe : on dénombre souvent le complémentaire (« au moins un » se traite par « aucun »).

5. Listes, arrangements, combinaisons

Soit $E$ un ensemble à $n$ éléments et $p \in \mathbb{N}$.

• $p$-listes (ordre compté, répétitions permises) : $n^{p}$.
• Arrangements (ordre compté, sans répétition, $p \leq n$) : $\dfrac{n!}{(n-p)!}$ ; en particulier $n!$ permutations de $E$.
• Combinaisons (parties à $p$ éléments, sans ordre) : $\dbinom{n}{p} = \dfrac{n!}{p!\,(n-p)!}$ si $0 \leq p \leq n$, et $0$ sinon.

Propriétés : $\dbinom{n}{p} = \dbinom{n}{n-p}$ et, pour $1 \leq p \leq n-1$, la formule de Pascal $\dbinom{n}{p} = \dbinom{n-1}{p-1} + \dbinom{n-1}{p}$.

6. Formule du binôme de Newton

Pour tous réels (ou complexes) $a$ et $b$ et tout $n \in \mathbb{N}$ :
$$(a+b)^{n} = \sum_{k=0}^{n} \binom{n}{k} a^{k} b^{n-k}$$
La somme comporte $n+1$ termes. Conséquences : $\sum_{k=0}^{n} \binom{n}{k} = 2^{n}$ et, pour $n \geq 1$, $\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$.
La formule reste valable pour deux matrices carrées $A$ et $B$ qui commutent ($AB = BA$).