Exercice 47

Fixons $n$. Les deux sommes intérieures portent sur les couples $(p, q)$ tels que $0 \leqslant p \leqslant q \leqslant n$ : on les intervertit, puis l'on pose $r = n - q$, qui décrit $[\![0\,;n-p]\!]$ : $$\sum_{q=0}^{n} \sum_{p=0}^{q} \binom{n}{p}\binom{n-p}{n-q} = \sum_{p=0}^{n} \binom{n}{p} \sum_{q=p}^{n} \binom{n-p}{n-q} = \sum_{p=0}^{n} \binom{n}{p}\,2^{n-p} = 3^{n}.$$ La dernière égalité est la formule du binôme pour $(1 + 2)^{n}$. Il reste une somme géométrique. $$\boxed{\sum_{n=0}^{m} 3^{n} = \frac{3^{m+1} - 1}{2}}$$ Le nombre $3^{n}$ s'interprète : la somme intérieure compte les couples $(P, Q)$ de parties d'un ensemble à $n$ éléments telles que $P \subset Q$, et chaque élément a trois possibilités, être dans $P$, dans $Q \setminus P$, ou hors de $Q$.