Formule d'itération de Pascal

En mathématiques, plus précisément en combinatoire, la formule d'itération de Pascal^[1], appelée aussi formule de la gouttière (ou formule de la crosse de hockey par traduction de l'anglais «Hockey-stick identity») est une formule exprimant la somme de termes consécutifs d'une colonne du triangle de Pascal.

La formule donne le résultat d'une somme finie de termes consécutifs d'une colonne du triangle de Pascal, débutant au premier terme non nul, comme étant le coefficient binomial situé à droite et en-dessous du dernier terme.

Pour les termes de la colonne p, allant de la ligne p jusqu'à la ligne n, la formule s'écrit :

${\displaystyle \sum _{k=p}^{n}{k \choose p}={n+1 \choose p+1}\quad {\text{, pour }}n\geqslant p\geqslant 0}$.

En utilisant la complétion du triangle de Pascal par des termes nuls, on peut aussi l'écrire : ${\displaystyle \sum _{k=0}^{n}{k \choose p}={n+1 \choose p+1}\quad {\text{, pour }}n,p\geqslant 0}$.

Et en utilisant la symétrie des coefficients binomiaux, on obtient la somme d'une diagonale descendante : ${\displaystyle \sum _{k=p}^{n}{k \choose {k-p}}={n+1 \choose p+1}\quad {\text{, pour }}n\geqslant p}$.

L'expression « formule d'itération de Pascal » est une abréviation de « formule d'itération de la relation de Pascal » ; on trouve aussi la forme « formule de Pascal itérée » ^[2].

Les expressions : formule « de la gouttière », ou « de la crosse de Hockey », viennent de l'analogie entre la situation des termes de la somme et de son résultat dans le triangle de Pascal et la forme des objets correspondants (voir figure ci-contre).

La formule est appelée « sommation sur l'indice du haut » dans le livre Concrete Mathematics^[3].

Diverses démonstrations utilisent la relation de Pascal :

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}$

On a ${\displaystyle {n+1 \choose p+1}={n \choose p}+{n \choose p+1}={n \choose p}+{n-1 \choose p}+{n-1 \choose p+1}=\cdots ={n \choose p}+{n-1 \choose p}+\cdots +{n-k \choose p}+{n-k \choose p+1}}$.

En faisant ${\displaystyle k=n-p}$, on obtient ${\displaystyle {n+1 \choose p+1}={n \choose p}+{n-1 \choose p}+\cdots +{p \choose p}+\underbrace {p \choose p+1} _{0}}$, ce qui donne bien la formule.

${\displaystyle {\begin{aligned}\sum _{k=\color {blue}p}^{n}{\binom {k}{p}}&=\sum _{k=p}^{n}\left[{\binom {k+1}{p+1}}-{\binom {k}{p+1}}\right]\\&={\binom {n+1}{p+1}}-\underbrace {\binom {p}{p+1}} _{0}&&\\&={\binom {n+1}{p+1}}.\end{aligned}}}$

Cette démonstration nécessite de connaître la formule a priori.

Initialisation ; pour ${\displaystyle n=p}$ la formule s'écrit ${\displaystyle 1=1}$.

Hérédité ; hypothèse de récurrence :

${\displaystyle \sum _{k=p}^{n}{k \choose p}={n+1 \choose p+1}}$.

Alors

${\displaystyle \sum _{k=p}^{n+1}{k \choose p}=\left(\sum _{k=p}^{n}{k \choose p}\right)+{n+1 \choose p}={n+1 \choose p+1}+{n+1 \choose p}={n+2 \choose p+1},}$

ce qui achève la récurrence.

D'après la formule des séries géométriques, on a :

${\displaystyle (1+X)^{p}+(1+X)^{p+1}+\dots +(1+X)^{n}={\frac {(1+X)^{n+1}-(1+X)^{p}}{X}}}$

Or dans le premier membre, le coefficient de ${\displaystyle X^{p}}$ est égal à ${\displaystyle \sum _{k=p}^{n}{\dbinom {k}{p}}}$, et dans le second membre, il est égal à ${\displaystyle {\dbinom {n+1}{p+1}}}$, d'où la formule.

Combien existe-t-il de sous-ensembles de ${\displaystyle [\![1,n+1]\!]}$ ayant ${\displaystyle p+1}$ éléments ?

• méthode 1 : ${\displaystyle {\dbinom {n+1}{p+1}}}$
• méthode 2 : en raisonnant sur le maximum égal à ${\displaystyle k+1}$ (avec ${\displaystyle p\leqslant k\leqslant n}$) du sous-ensemble ; une fois ce maximum fixé il reste ${\displaystyle p}$ éléments à choisir parmi ${\displaystyle k}$, soit ${\displaystyle {\dbinom {k}{p}}}$ choix possibles ; on obtient donc au total ${\displaystyle \sum _{k=p}^{n}{\dbinom {k}{p}}}$ sous-ensembles ^[4].

En écrivant les coefficients binomiaux sous leur forme étendue, la formule s'écrit :

${\displaystyle \sum _{k=p}^{n}k(k-1)\cdots (k-p+1)={\frac {(n+1)n...(n-p+1)}{p+1}}}$.

Pour ${\displaystyle p=1}$ on retrouve la somme des ${\displaystyle n}$ premiers entiers : ${\displaystyle \sum _{k=1}^{n}k={\frac {(n+1)n}{2}}}$ ; pour ${\displaystyle p=2}$ elle s'écrit ${\displaystyle \sum _{k=2}^{n}k(k-1)={\frac {(n+1)n(n-1)}{3}}}$, ce qui permet d'obtenir la somme des premiers carrés ${\displaystyle \sum _{k=1}^{n}k^{2}}$, et ainsi de suite pour les sommes des premières puissances.

Et en utilisant le théorème de sommation des équivalents, on obtient ${\displaystyle \sum _{k=1}^{n}k^{p}\sim {\frac {n^{p+1}}{p+1}}}$.

Pour ${\displaystyle n\geqslant p\geqslant 2}$ , on a

${\displaystyle \sum _{k=p}^{n}{\frac {1}{k \choose p}}={\frac {p}{p-1}}\left(1-{\frac {1}{n \choose p-1}}\right)}$, dont ont déduit la somme infinie : ${\displaystyle \sum _{k=p}^{\infty }{\frac {1}{k \choose p}}={\frac {p}{p-1}}}$.

On obtient cette relation par télescopage à partir de la relation ${\displaystyle {\frac {1}{k \choose p}}={\frac {p}{p-1}}\left({\frac {1}{k-1 \choose p-1}}-{\frac {1}{k \choose p-1}}\right)}$, laquelle vient de ${\displaystyle (p-1){k-1 \choose p-1}{k \choose p-1}=p{k-1 \choose p-2}{k \choose p}}$.

La somme infinie s'écrit aussi : ${\displaystyle \sum _{k=p}^{\infty }{\frac {1}{k(k-1)\cdots (k-p+1)}}={\frac {1}{(p-1)(p-1)!}}}$.

• Triangle de Pascal
• Identité de Vandermonde
• Q-analogue de la formule d'itération de Pascal

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hockey-stick identity » (voir la liste des auteurs).

• Portail des mathématiques