Formule du CRIBLE - Exercice 1

Nous allons réaliser une démonstration par récurrence.
Soit $$n$$ un nombre entiers naturel non nul.
Notons par $$P(n)$$ la propriété suivante :
$$P(n) : \mathrm{card}\left( \bigcup_{i=1}^{n} A_i \right) = \sum_{k = 1}^{n} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right)$$
$${\color{blue}{\bf{\bullet \,\, Etape \,\, 1 : Initialisation}}}$$
On pose $$n = 1$$. Dans ce cas, on a :
$$\mathrm{card}\left( \bigcup_{i=1}^{n} A_i \right) = \mathrm{card}\left( \bigcup_{i=1}^{1} A_i \right) = \mathrm{card}\left( A_1 \right)$$
De plus :
$$\sum_{k = 1}^{n} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) = \sum_{k = 1}^{1} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, 1} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right)$$
Donc on en déduit que :
$$\sum_{k = 1}^{n} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) = (-1)^{1+1} \sum_{1} \mathrm{card}\left( \bigcap_{p=1}^{1} A_{i_{p}} \right) = (-1)^2 \times \mathrm{card}\left( A_1 \right) = \mathrm{card}\left( A_1 \right)$$
Ainsi, on constate que $$P(n=1)$$ est vraie, donc la propriété $$P(n)$$ est bien initialisée.
$${\color{blue}{\bf{\bullet \bullet \,\, Etape \,\, 2 : Transmission}}}$$
Soit $$n \in \mathbb{N}^\star$$. On suppose que la propriété $$P(n)$$ est effectivement vraie. Démontrons que, sous cette vérité de $$P(n)$$, on a également $$P(n+1)$$ qui est également vraie.
On considère la famille $$(A_i)_{1 \leqslant i \leqslant n+1}$$ d'ensembles finis. et on note par $$B$$ l'ensemble union suivant : $$B = \bigcup_{i=1}^{n} A_i$$. Donc on a :
$$\mathrm{card}\left( \bigcup_{i=1}^{n+1} A_i \right) = \mathrm{card}\left( B \cup A_{n+1} \right) = \mathrm{card}\left( B \right) + \mathrm{card}\left( A_{n+1} \right) - \mathrm{card}\left( B \cap A_{n+1} \right)$$
Ce qui s'écrit également comme :
$$\mathrm{card}\left( \bigcup_{i=1}^{n+1} A_i \right) = \mathrm{card}\left( \left(\bigcup_{i=1}^{n} A_i \right) \cup A_{n+1} \right) = \mathrm{card}\left( \bigcup_{i=1}^{n} A_i \right) + \mathrm{card}\left( A_{n+1} \right) - \mathrm{card}\left( \left( \bigcup_{i=1}^{n} A_i \right) \cap A_{n+1} \right)$$
Donc, par clarté d'écriture, on a (en tenant compte du fait que l'intersection est commutative) :
$$\mathrm{card}\left( \bigcup_{i=1}^{n+1} A_i \right) = \mathrm{card}\left( \bigcup_{i=1}^{n} A_i \right) + \mathrm{card}\left( A_{n+1} \right) - \mathrm{card}\left( A_{n+1} \cap \left( \bigcup_{i=1}^{n} A_i \right) \right)$$
La propriété $$P(n)$$ étant supposée vraie, on a donc :
$$\mathrm{card}\left( \bigcup_{i=1}^{n+1} A_i \right) = \sum_{k = 1}^{n} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) + \mathrm{card}\left( A_{n+1} \right) - \mathrm{card}\left( A_{n+1} \cap \left( \bigcup_{i=1}^{n} A_i \right) \right)$$
Puis, en tenant compte de la distributivité de l'union et de l'intersection, on a :
$$A_{n+1} \cap \left( \bigcup_{i=1}^{n} A_i \right) = \bigcup_{i=1}^{n} \left( A_{n+1} \cap A_i \right)$$
Ce qui nous permet d'écrire que :
$$\mathrm{card}\left( \bigcup_{i=1}^{n+1} A_i \right) = \sum_{k = 1}^{n} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) + \mathrm{card}\left( A_{n+1} \right) - \mathrm{card}\left( \bigcup_{i=1}^{n} \left( A_{n+1} \cap A_i \right) \right)$$
L'expression du dernier terme $$\mathrm{card}\left( \bigcup_{i=1}^{n} \left( A_{n+1} \cap A_i \right) \right)$$ peut être exprimée différemment grace à la propriété $$P(n)$$ qui, nous le rappelons, est supposée vraie. En effet, il suffit d'effectuer (dans $$P(n)$$) la substitution $$A_i \leftrightsquigarrow \left( A_{n+1} \cap A_i \right)$$. Dans ce cas, on a :
$$\mathrm{card}\left( \bigcup_{i=1}^{n} \left( A_{n+1} \cap A_i \right) \right) = \sum_{k = 1}^{n} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} \left( A_{n+1} \cap A_{i_{p}} \right) \right) \right)$$
Ce qui s'écrit également comme :
$$\mathrm{card}\left( \bigcup_{i=1}^{n} \left( A_{n+1} \cap A_i \right) \right) = \sum_{k = 1}^{n} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_{k+1} \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{k+1} A_{i_{p}} \right) \right)$$
Posons $$K = k+1$$. Dans ce cas le terme $$K$$ va de $$2$$ à $$n+1$$. Et on obtient :
$$\mathrm{card}\left( \bigcup_{i=1}^{n} \left( A_{n+1} \cap A_i \right) \right) = \sum_{K = 2}^{n+1} \left( (-1)^{K} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right)$$
Ceci nous permet donc d'écrire que :
$$\begin{array}{rcl} \mathrm{card}\left( \displaystyle{\bigcup_{i=1}^{n+1}} A_i \right) & = & \displaystyle{\sum_{k = 1}^{n}} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) \\ & + & \mathrm{card}\left( A_{n+1} \right) \\ & - & \displaystyle{\sum_{K = 2}^{n+1}} \left( (-1)^{K} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right) \\ \end{array}$$
Soit encore :
$$\begin{array}{rcl} \mathrm{card}\left( \displaystyle{\bigcup_{i=1}^{n+1}} A_i \right) & = & \displaystyle{\sum_{k = 1}^{n}} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) \\ & + & \mathrm{card}\left( A_{n+1} \right) \\ & + & \displaystyle{\sum_{K = 2}^{n+1}} \left( -(-1)^{K} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right) \\ \end{array}$$
Ou de même :
$$\begin{array}{rcl} \mathrm{card}\left( \displaystyle{\bigcup_{i=1}^{n+1}} A_i \right) & = & \displaystyle{\sum_{k = 1}^{n}} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) \\ & + & \mathrm{card}\left( A_{n+1} \right) \\ & + & \displaystyle{\sum_{K = 2}^{n+1}} \left( (-1)^{K+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right) \\ \end{array}$$
Dans la dernière somme précédente, celle portant sur $$K$$ qui va de $$2$$ à $$n+1$$, examinons ce que nous donnerait le terme qui corresponderait à $$K = 1$$. Nous avons donc :
$$(-1)^{1+1} \sum_{i_1 \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{1} A_{i_{p}} \right) = (-1)^{2} \sum_{i_1 \, = \, n+1} \mathrm{card}\left( A_{i_{1}} \right) = 1 \times \mathrm{card}\left( A_{n+1} \right) = \mathrm{card}\left( A_{n+1} \right)$$
Ce qui nous permet d'écrire que :
$$\mathrm{card}\left( A_{n+1} \right) + \displaystyle{\sum_{K = 2}^{n+1}} \left( (-1)^{K+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right) = \displaystyle{\sum_{K = 1}^{n+1}} \left( (-1)^{K+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right)$$
Ainsi, on peut donc écrire que :
$$\begin{array}{rcl} \mathrm{card}\left( \displaystyle{\bigcup_{i=1}^{n+1}} A_i \right) & = & \displaystyle{\sum_{k = 1}^{n}} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) \\ & + & \displaystyle{\sum_{K = 1}^{n+1}} \left( (-1)^{K+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right) \\ \end{array}$$
Comme $$n$$ est un nombre entier naturel, la condition $$i_k \, \leqslant \, n$$, présente dans la première somme, est identique à $$i_k \, < \, n+1$$. De fait, on a :
$$\begin{array}{rcl} \mathrm{card}\left( \displaystyle{\bigcup_{i=1}^{n+1}} A_i \right) & = & \displaystyle{\sum_{k = 1}^{n}} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, < \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) \\ & + & \displaystyle{\sum_{K = 1}^{n+1}} \left( (-1)^{K+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right) \\ \end{array}$$
Toujours dans la première somme, le fait d'arrêter la sommation à $$n$$ et qu'il est impossible d'accéder au terme qui serait indicé par $$n+1$$, nous permet d'écrire que :
$$\begin{array}{rcl} \mathrm{card}\left( \displaystyle{\bigcup_{i=1}^{n+1}} A_i \right) & = & \displaystyle{\sum_{k = 1}^{n+1}} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, < \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right) \\ & + & \displaystyle{\sum_{K = 1}^{n+1}} \left( (-1)^{K+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_K \, = \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{K} A_{i_{p}} \right) \right) \\ \end{array}$$
On constate que les deux sommes précédentes sont les deux cas de la disjonction logique entre $$i_k \, < \, n+1$$ (la première somme) et $$i_K \, = \, n+1$$ (la seconde somme). On peut donc les réunir sous la condition unique $$i_k \, \leqslant \, n+1$$. Ainsi, on obtient :
$$\mathrm{card}\left( \displaystyle{\bigcup_{i=1}^{n+1}} A_i \right) = \displaystyle{\sum_{k = 1}^{n+1}} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n+1} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right)$$
Donc, sous l'hypothèse que la propriété $$P(n)$$ soit vraie, on constate que a propriété $$P(n+1)$$ est également vraie. On a donc démontrer que $$P(n) \Longrightarrow P(n+1)$$. Ainsi la propriété étudiée est bien transmissible.
$${\color{blue}{\bf{\bullet \bullet \bullet \,\, Etape \,\, 3 : Conclusion}}}$$
En vertu des axiomes de la récurrence, la propriété $$P(n) : \mathrm{card}\left( \bigcup_{i=1}^{n} A_i \right) = \sum_{k = 1}^{n} \left( (-1)^{k+1} \sum_{1 \, \leqslant \, i_1 \, < \, \cdots \, < \, i_k \, \leqslant \, n} \mathrm{card}\left( \bigcap_{p=1}^{k} A_{i_{p}} \right) \right)$$ est vrair pour tout nombre entier naturel non nul $$n$$.