title: Formule d'itération de Pascal
text: # 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$.
  
  ## 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)!}}$.
  
  