On note pₙ le nombre de parties d'un ensemble à n éléments (la partie…

Exercice supplémentaire · niveau 3 (difficile) · mathématiques (première), chapitre 1 — Vocabulaire ensembliste et logique · Le raisonnement par récurrence (programme de terminale)

Énoncé

On note $p_{n}$ le nombre de parties d'un ensemble à $n$ éléments (la partie vide et l'ensemble tout entier comprises).

Calculer $p_{0}$ , $p_{1}$ , $p_{2}$ , $p_{3}$ en listant les parties.
Justifier que $p_{n + 1} = 2 p_{n}$ : ajouter un élément, c'est doubler le nombre de parties (celles qui le contiennent, celles qui ne le contiennent pas).
En déduire que $p_{n} = 2^{n}$ .

Corrigé

1. L'ensemble vide a une seule partie, lui-même : $p_{0} = 1$ . Pour ${a}$ : $\emptyset$ et ${a}$ , donc $p_{1} = 2$ . Pour ${a; b}$ : $\emptyset$ , ${a}$ , ${b}$ , ${a; b}$ , donc $p_{2} = 4$ . Pour ${a; b; c}$ , on ajoute aux quatre précédentes les quatre parties obtenues en y adjoignant $c$ : $p_{3} = 8$ . 2. Soit $E$ un ensemble à $n$ éléments et $E^{'} = E \cup {x}$ à $n + 1$ éléments. Les parties de $E^{'}$ se répartissent en deux familles sans recouvrement : celles qui ne contiennent pas $x$ — ce sont exactement les parties de $E$ , au nombre de $p_{n}$ — et celles qui contiennent $x$ , chacune s'écrivant $A \cup {x}$ avec $A$ partie de $E$ , également au nombre de $p_{n}$ . D'où $p_{n + 1} = 2 p_{n}$ . 3. La suite $(p_{n})$ est donc géométrique de raison $2$ et de premier terme $p_{0} = 1$ : $p_{n} = 2^{n}$ . Contrôle : $p_{3} = 2^{3} = 8$ , conforme au dénombrement de la question 1. Prolongement : on retrouvera ce $2^{n}$ en terminale, en associant à chaque partie la liste des $n$ réponses « oui / non » à la question « cet élément y est-il ? ».

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.