Compter les couples de parties emboîtées

Ce qu'on montre. Une identité, par double dénombrement : un même ensemble compté de deux façons.

Notons $\mathcal{E}=\{(A,B)\mid A\subset B\subset E\}$.

Premier comptage : par le cardinal de $B$. Découpons $\mathcal{E}$ selon $k=\mathrm{card}B$, avec $0\le k\le n$. Ces cas sont deux à deux disjoints et recouvrent $\mathcal{E}$.

• Choisir $B$ de cardinal $k$ : $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ possibilités, par définition du coefficient binomial.
• $B$ étant fixé, choisir $A\subset B$ : c'est choisir une partie d'un ensemble à $k$ éléments, soit $2^k$ possibilités.

Ces deux choix étant successifs et indépendants, il y a $\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k$ couples pour un $k$ donné, d'où $$\mathrm{card}\mathcal{E}=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k.$$

Second comptage : élément par élément. Se donner $(A,B)$ avec $A\subset B$, c'est décider, pour chaque $x\in E$, de l'une des trois situations mutuellement exclusives : $$x\in A(\text{donc }x\in B),x\in B\text{ et }x\notin A,x\notin B.$$ La quatrième combinaison, $x\in A$ et $x\notin B$, est interdite par $A\subset B$ : c'est exactement là que l'hypothèse agit. Les $n$ décisions sont indépendantes, à $3$ issues chacune : $$\mathrm{card}\mathcal{E}=3^n.$$

Conclusion. Les deux comptages portent sur le même ensemble, donc $$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k=3^n.$$

Contrôle par le binôme. La formule du binôme donne directement ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k{1}^{n-k}=(2+1{)}^n=3^n$ : les deux voies concordent. Vérification numérique pour $n=2$ : $1+2\times 2+4=9=3^2$.