Somme de coefficients binomiaux

Publié le 19/11/16

Soient {p,q\in\mathbb{N}}. Montrer que : {\displaystyle\sum_{k=p}^{q}\displaystyle\binom{k}{p}=\displaystyle\binom{q+1}{p+1}}.
  • Première méthode :
    On procède par récurrence sur q, à {p} fixé.
    La propriété est vraie au pas initial {q=p}.
    Si elle est vraie au rang {q\ge p}, alors : {\displaystyle\sum_{k=p}^{q+1}\binom{k}{p}= \displaystyle\sum_{k=p}^q\displaystyle\binom kp+\displaystyle\binom{q+1}{p}=\displaystyle\binom{q+1}{p+1}+\displaystyle\binom{q+1}{p}=\displaystyle\binom{q+2}{p+1}}Ce qui prouve la propriété au rang {q+1} et achève la récurrence.
  • Deuxième méthode :
    Pour tout {k\ge p}, on a: {\displaystyle\binom{k}{p}=\displaystyle\binom{k+1}{p+1}-\displaystyle\binom{k}{p+1}}. On en déduit:
    {\displaystyle\sum_{k=p}^q\displaystyle\binom{k}{p}=\displaystyle\sum_{k=p}^q\left(\displaystyle\binom{k+1}{p+1}-\displaystyle\binom{k}{p+1}\right)=\displaystyle\binom{q+1}{p+1}-\displaystyle\binom{p}{p+1}\displaystyle\binom{q+1}{p+1}}
  • Troisième méthode :
    Soit {\mathcal{A}} l’ensemble des parties de {[[ 1,q+1]\!]} qui ont {p+1} éléments.
    On sait que {\text{card}(\mathcal{A})=\displaystyle\binom{q+1}{p+1}}. Soit {\mathcal{A}_k=\{X\in\mathcal{A},\;\max(X)=k+1\}}.
    Former {X\in\mathcal{A}_k}, c’est choisir les {p} éléments de {X\setminus\{k+1\}} dans {[\![ 1,k]\!]}.
    Pour cela, il y a {\displaystyle\binom{k}{p}} possibilités.
    Ainsi {\text{card}(\mathcal{A})=\displaystyle\sum_{k=p}^{q}\text{card}(\mathcal{A}_k)}, c’est-à-dire: {\displaystyle\binom{q+1}{p+1}=\displaystyle\sum_{k=p}^{q}\displaystyle\binom{k}{p}}.