Formule d'itération de Pascal

En mathématiques, plus précisément en combinatoire, la formule d'itération de Pascal, 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.

Formulation

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 :

$\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 : $\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 : $\sum _{k=p}^{n}{k \choose {k-p}}={n+1 \choose p+1}\quad {\text{, pour }}n\geqslant p$.

Les cases rouges sont celles utilisées par la formule pour $n=5,p=2$ ; en bleu, cas d'une diagonale descendante pour les mêmes valeurs.

Explication des appellations

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 » .

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.

Démonstrations

À partir de la relation de Pascal

Diverses démonstrations utilisent la relation de Pascal :

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

Par itération de cette relation

On a ${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 $k=n-p$, on obtient ${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.

Par somme télescopique

${\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}}$

Par récurrence sur n

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

Initialisation ; pour $n=p$ la formule s'écrit $1=1$.

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

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

Alors

$\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.

Utilisation de la formule du binôme

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

$(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 $X^{p}$ est égal à $\sum _{k=p}^{n}{\dbinom {k}{p}}$, et dans le second membre, il est égal à ${\dbinom {n+1}{p+1}}$, d'où la formule.

Démonstration combinatoire

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

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

Applications

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

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

Pour $p=1$ on retrouve la somme des $n$ premiers entiers : $\sum _{k=1}^{n}k={\frac {(n+1)n}{2}}$ ; pour $p=2$ elle s'écrit $\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 $\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 $\sum _{k=1}^{n}k^{p}\sim {\frac {n^{p+1}}{p+1}}$.

Somme des inverses des termes d'une colonne du triangle de Pascal

Pour $n\geqslant p\geqslant 2$ , on a

$\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 : $\sum _{k=p}^{\infty }{\frac {1}{k \choose p}}={\frac {p}{p-1}}$.

On obtient cette relation par télescopage à partir de la relation ${\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 $(p-1){k-1 \choose p-1}{k \choose p-1}=p{k-2 \choose p-1}{k \choose p}$.

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

Voir aussi

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

Références

• (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).